Merge sort on divide-and-conquer, vakaa lajittelualgoritmi, joka toimii takuutussa O(n log n) ajassa. Se jakaa taulukon puoliksi, lajittelee jokaisen puoliskon rekursiivisesti ja yhdistää sitten kaksi lajiteltua puoliskoa.
Yksittäinen elementti on jo lajiteltu (perustapaus). Kahden lajiteltujen luettelon yhdistäminen on lineaarista, ja teemme log n tasoa yhdistämistä.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Ihanteellinen, kun tarvitset vakautta tai takuutettua O(n log n), sekä linkitetyille listoille ja ulkoiseen lajitteluun valtavista tiedostoista. Ylimääräinen O(n) muisti on sen pääasiallinen haitta.
Merge sort takaa O(n log n) riippumatta syötteestä, toisin kuin quicksortin O(n²) pahin tapaus.
Sen vakaus säilyttää yhtä suurten avainten suhteellisen järjestyksen, mikä on tärkeää moniavainlajittelussa.
Yhdistymisvaihe on uudelleenkäytettävä primitiivi, ja divide-and-conquer-rakenne on malli, jonka käytät uudelleen kaikkialla.