Birleştirmeli sıralama (mergesort)
Listeyi ikiye böl, her yarıyı sırala, sonra birleştir — her durumda, istisnasız O(n log n).
1945’te John von Neumann tarafından tanımlandı; bu da onu hâlâ üretimde çalışan en eski algoritmalardan biri yapar. Birleştirme adımı, önceden sıralı iki listeyi gezer ve her seferinde iki baştaki elemandan küçüğünü alır; bu doğrusaldır. Özyineleme log n derinliğindedir; çarpım, garanti edilen karmaşıklığı verir.
İki özellik onu yerinden etmeyi zorlaştırır. Birincisi kararlı olmasıdır: eşit elemanlar göreli sıralarını korur; bu, birden çok alana göre art arda sıralama yaparken şarttır. İkincisi yalnızca ardışık okumasıdır; bellekten büyük veriler için standart tercih bu yüzden odur: diskteki ve şeritteki harici sıralamalar hâlâ mergesort’a dayanır. Bedeli O(n) ek bellektir; Quicksort neredeyse hiç ek bellek istemez ama en kötü durumda ikinci dereceden zamana düşer. Python ve Java’nın varsayılan sıralamaları, altında mergesort bulunan melez Timsort’u kullanır.