Metode Merge Sort
Metode ini memanfaatkan keteraturan yang diperoleh dari hasil merging dua buah array. Suatu array Nilai yang mempunyai N elemen (Nilai[0..N-1]) dianggap terdiri dari N array yang masing-masing terdiri dari satu elemen. Untuk pasangan array yang berdekatan kita lakukan merging sehingga diperoleh N/2 buah array yang masing-masing array memiliki 2 elemen (jika N ganjil, akan terdapat sebuah array dengan 1 elemen). Pada saat melakukan proses merging dilakukan pengaturan posisi dengan cara elemen yang lebih kecil diletakkan di posisi awal (untuk pengurutan secara menaik) dan elemen yang lebih besar diletakkan di posisi awal(untuk pengurutan secara menurun). Kemudian dilakukan merging kembali untuk setiap pasanga array seperti cara di atas sehingga kita peroleh N/2 buah array yang masing-masing array memiliki 4 elemen. Langkah ini kita teruskan hingga kita memperoleh sebuah array yang sudah dalam keadaan terurut.
Misalkan kita memiliki array Nilai[0..13] = {45, 12, 4, 78, 90, 74, 40, 20, 10, 15, 25, 22, 95, 81} maka dengan menggunakan metode Merge Sort secara menaik dapat dilakukan seperti pada gambar.
