Merge Sort

Merge sort selalu O(n log n) karena pohon pembagian memiliki log n level dan setiap level menggabungkan total n elemen. Kasus terbaik maupun terburuk sama karena pembagian tidak bergantung pada isi data. Kekurangannya, merge memerlukan memori tambahan O(n), sehingga space complexity total menjadi O(n).