Birləşdirmə çeşidləməsi "böl və hökm sür" alqoritminin klassik nümunəsidir: massivi yarıya bölürük, yarıları rekursiv çeşidləyirik və iki çeşidlənmiş yarını O(n) vaxtda birləşdiririk. İş vaxtı hər halda O(n log n)-dir, dayanıqlıdır, lakin O(n) əlavə yaddaş tələb edir. Rekursiya ağacları üçün bax: böl və hökm sür.
İki çeşidlənmiş siyahının birləşdirilməsi
Hər iki siyahının başına baxırıq və kiçik elementi nəticəyə köçürürük. Bir siyahı qurtaranda digərinin qalığını əlavə edirik: o, artıq çeşidlənib. Bu, O(n + m) vaxt aparır. Bərabərlikdə sol siyahıdan götürürük, buna görə birləşdirmə dayanıqlıdır.
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out += left[i:]
out += right[j:]
return out
print(merge([1, 4, 7], [2, 3, 9]))
print(merge([], [5]))
print(merge([(1, "a"), (2, "a")], [(1, "b"), (2, "b")]))[1, 2, 3, 4, 7, 9]
[5]
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]Rekursiv birləşdirmə çeşidləməsi
0 və ya 1 elementli siyahı artıq çeşidlənib. Əks halda siyahını yarıya bölürük, yarıları çeşidləyirik və birləşdiririk.
