Contoh Program Algoritma Merge Sort di C++ Beserta Penjelasan

Contoh Program Algoritma Merge Sort di C++ – Merge Sort merupakan salah satu algoritma yang digunakan untuk melakukan pengurutan sebuah data, baik secara ascending maupun descending

Algoritma ini ditemukan pada tahun 1945 oleh  John von Neuman dan masih populer hingga saat ini.

Apa itu algoritma Merge Sort

Algoritma Merge Sort adalah salah satu algoritma modern yang mirip seperti algoritma Quick Sort.

Keduanya sama-sama menggunakan metode Devide and Conquer. dimana sebuah list akan dipecah menggunakan fungsi rekursif

pertama kita akan membuat 2 blok dari sebuah list, dengan cara membelahnya menjadi 2 bagian sama rata, jika ternyata list tersebut jumlahnya ganjil, maka akan dibulatkan.

setelah menjadi 2 blok, masing masing blok akan di pecah kembali menggunakan fungsi rekursiv hingga setiap blok hanya memiliki 1 index list.

jika sudah, kita akan menyatukan 2 blok menjadi satu dan melakukan sorting antara 2 elemen blok tadi, jika ascending maka index dengan angka paling kecil akan berada disebelah kiri dan sebaliknya.

kita akan mengulang proses perbandingan tersebut hingga hanya tersisa 1 blok dengan index yang sudah tersorting.

Penjelasan Algoritma Merge Sort

Anggap saja kita memiliki List dengan urutan acak, seperti berikut:

sesuai dengan yang saya katakan diatas, algoritma ini menggunakan metode devide and conquer, jadi kita akan memecah List ini menjadi 2 bagian sama rata.

apakah elemen tersebut sudah menjadi elemen tunggal? tentu saja belum, maka kita akan membagi kembali sampai kita mendapat elemen tunggal dari setiap index List.

sekarang, semua elemen sudah menjadi elemen tunggal, selanjutnya kita akan melakukan sorting dengan menggunakan kebalikan dari metode devide and conquer, dimana kita akan melakukan perbandingan antara 2 elemen dan menggabungkannya menjadi elemen baru

selanjutnya kita akan membandingkan 2 elemen kembali hingga semua item dalam List tersusun Ascending.

lakukan lagi hingga semua data berhasil tersusun.

Baca juga: Contoh Program Algoritma Quick Sort

Kelebihan Algoritma Merge Sort

• Performa sangat bagus untuk List yang memiliki banyak index
• memiliki waktu pengerjaan yang konsisten (worst case,average case,best case)

Kekurangan Algoritma Merge Sort

• Performa buruk untuk list dengan index sendikit dibanding algoritma sorting lainnya seperti bubble sort dan insertion sort
• Jika data sudah tersorting sejak awal, maka ia akan tetap melakukan sorting dari awal.
• Menggunakan memory lebih untuk melakukan split data

Contoh Program Merge Sort C++

Output

itulah Contoh program algoritma merge sort beserta penjelasannya, smoga bermanfaat, kamu jiga bisa mencari algoritma c++ lainnya disini