Sortowanie przez scalanie

Sortowanie przez scalanie (ang. merge sort) to algorytm sortowania, który stosuje podejście dziel i zwyciężaj. Został odkryty przez Johna von Neumanna i doskonale sprawdza się przy sortowaniu dużych zbiorów danych. Działa poprzez rekurencyjne dzielenie tablicy wejściowej na mniejsze podtablice i sortowanie tych podtablic, a następnie ponowne ich scalanie w celu uzyskania posortowanej tablicy.

Mówiąc prościej – proces sortowania przez scalanie polega na podzieleniu tablicy na dwie połowy, posortowaniu każdej połowy, a następnie ponownym połączeniu posortowanych połówek. Proces ten jest powtarzany, aż cała tablica zostanie posortowana.

Złożoność czasowa: O(n log(n))

Złożoność pamięciowa: O(n)

Kroki algorytmu:

• Dziel: Dzielenie tablicy rekurencyjnie na dwie połowy, aż do momentu, w którym nie będzie już możliwości dalszego podziału.
• Sortuj: Każda podtablica jest sortowana indywidualnie za pomocą algorytmu sortowania przez scalanie.
• Scal: Posortowane podtablice są ponownie łączone w posortowanej kolejności.

Działanie algorytmu

Implementacja algorytmu sportowania przez scalanie w Pythonie:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        # utworz tablice tymczasowe
        left = arr[:mid]
        right = arr[mid:]

        # rekurencyjne sortowanie obu czesci tablicy
        merge_sort(left)
        merge_sort(right)

        # dwa iteratory do przechodzenia przez dwie połówki
        i = 0
        j = 0
        
        # iterator dla glownej tabeli
        k = 0
        
        # polacz ponownie tablice tymczasowe
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
              arr[k] = left[i]
              i += 1
            else:
                arr[k] = right[j]
                j += 1
           
            k += 1

        # skopiuj pozostale wartosci
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

arr_to_sort = [54,26,93,17,77,31,44,55,20]
merge_sort(arr_to_sort)
print(arr_to_sort)