Merge Sort - jak dzieci szybciej sprzątają klocki

A=[1,4,7], B=[2,3,8] → wynik=[]
1 < 2 → wynik=[1], A=[4,7]
4 > 2 → wynik=[1,2], B=[3,8]
4 > 3 → wynik=[1,2,3], B=[8]
4 < 8 → wynik=[1,2,3,4], A=[7]
7 < 8 → wynik=[1,2,3,4,7], A=[]
A puste → dokleja B → wynik=[1,2,3,4,7,8]

function mergeSort(tab) {
  if (tab.length <= 1) return tab;      // 1 klocek = posortowany

  const srodek = Math.floor(tab.length / 2);
  const lewa = mergeSort(tab.slice(0, srodek));    // zawołaj brata
  const prawa = mergeSort(tab.slice(srodek));      // zawołaj siostrę

  return scal(lewa, prawa);              // scalacie kupki
}

function scal(a, b) {
  const wynik = [];
  while (a.length && b.length) {
    wynik.push(a[0] <= b[0] ? a.shift() : b.shift());
  }
  return [...wynik, ...a, ...b];
}

Idea #

Merge sort to klasyczny algorytm divide and conquer:

1. Dziel tablicę na pół, rekurencyjnie.
2. Zwyciężaj - rekurencja kończy się na tablicy długości 1 (trywialnie posortowana).
3. Scalaj - dwie posortowane połowy łączysz w jedną posortowaną.

Złożoność #

• Czas: T(n) = 2T(n/2) + O(n) → O(n log n) (Master Theorem).
• Pamięć: O(n) - bufor na scalanie. Nie da się zrobić merge sortu in-place bez skomplikowania i utraty performance (in-place merge = O(n log² n)).
• Stabilność: tak - przy <= w porównaniu, elementy równe zachowują względną kolejność z inputu.

Implementacja w C# #

// title: MergeSort.cs
public static void Sort<T>(T[] array) where T : IComparable<T>
{
    if (array.Length <= 1) return;
    var buffer = new T[array.Length];
    SortRange(array, buffer, 0, array.Length - 1);
}

private static void SortRange<T>(T[] array, T[] buffer, int lo, int hi)
    where T : IComparable<T>
{
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;           // unikamy int overflow dla dużych indeksów
    SortRange(array, buffer, lo, mid);
    SortRange(array, buffer, mid + 1, hi);
    Merge(array, buffer, lo, mid, hi);
}

private static void Merge<T>(T[] array, T[] buffer, int lo, int mid, int hi)
    where T : IComparable<T>
{
    for (int k = lo; k <= hi; k++) buffer[k] = array[k];

    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid)                          array[k] = buffer[j++];
        else if (j > hi)                      array[k] = buffer[i++];
        else if (buffer[i].CompareTo(buffer[j]) <= 0)  array[k] = buffer[i++];
        else                                  array[k] = buffer[j++];
    }
}

Kluczowe szczegóły:

• Bufor alokowany raz na zewnątrz, przekazywany po referencji - nie alokujemy O(n log n) razy.
• mid = lo + (hi - lo) / 2 - unika integer overflow dla lo + hi > int.MaxValue.
• <= w porównaniu - zapewnia stabilność.

Quicksort vs merge sort #

	Merge sort	Quicksort
Worst case	O(n log n)	O(n²) (zły pivot)
Average	O(n log n)	O(n log n)
Pamięć	O(n)	O(log n) (stack)
In-place	nie (praktycznie)	tak
Stabilny	tak	nie
Cache locality	średnia	dobra (sekwencyjny dostęp w partition)

Quicksort w praktyce często szybszy przez cache locality i brak alokacji bufora - stąd Array.Sort w .NET używa introsortu (quicksort + heapsort jako fallback przy złej głębokości), nie merge sortu.

Kiedy merge sort wygrywa:

• Linked list - merge sort robi się w O(1) dodatkowej pamięci, quicksort jest niewygodny bez random access.
• External sorting - dane nie mieszczą się w RAM, merge sort dobrze mapuje się na “chunk-and-merge” z dysku.
• Stabilność wymagana - np. sortowanie rekordów po wielu kluczach kolejno (LINQ OrderBy().ThenBy() tego potrzebuje).

Dlaczego LINQ używa stabilnego sortu #

var data = new[] { (name: "Alice", age: 30), (name: "Bob", age: 30), (name: "Alice", age: 25) };
var sorted = data.OrderBy(x => x.age).ThenBy(x => x.name);

ThenBy działa tylko jeśli OrderBy jest stabilny - elementy o tym samym age zachowują kolejność z pierwszego sortu, a wtedy drugi sort je uporządkuje po nazwie bez rozbijania pierwotnego grupowania. Pod spodem OrderBy używa algorytmu zmodyfikowanego pod kątem stabilności.

Równoległy merge sort #

Każda z dwóch rekurencyjnych gałęzi jest niezależna - łatwy kandydat do Task Parallel Library:

private static async Task SortRangeParallel<T>(T[] array, T[] buffer, int lo, int hi, int depth)
    where T : IComparable<T>
{
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;

    if (depth > 0 && hi - lo > 10_000)
    {
        var left = Task.Run(() => SortRangeParallel(array, buffer, lo, mid, depth - 1));
        var right = Task.Run(() => SortRangeParallel(array, buffer, mid + 1, hi, depth - 1));
        await Task.WhenAll(left, right);
    }
    else
    {
        SortRange(array, buffer, lo, mid);
        SortRange(array, buffer, mid + 1, hi);
    }
    Merge(array, buffer, lo, mid, hi);
}

Dwa parametry tuningu:

• depth - ile poziomów rekurencji dzielimy równolegle (log2(cores) + 1).
• Próg hi - lo > 10_000 - dla małych partycji narzut tasków przewyższa zysk.

External merge sort - plik 100GB, RAM 16GB #

Algorytm:

1. Wczytaj chunk mieszczący się w RAM, posortuj in-memory, zapisz do tempfile.
2. Powtórz dla wszystkich chunków → masz N posortowanych plików.
3. Wielodrożne scalanie (k-way merge) - min-heap z pierwszymi elementami każdego pliku, wyciągasz minimum, dociągasz następne.

To jest dokładnie to, co robią bazy danych dla ORDER BY na dużych zbiorach nie mieszczących się w pamięci.

Pułapki #

• Alokacja bufora w każdym wywołaniu rekurencyjnym - O(n log n) garbage collection pressure zamiast O(n). Zawsze zewnętrzny bufor.
• Bottom-up merge sort - alternatywa bez rekurencji (iteracyjne scalania par o rosnącej szerokości), unikasz stosu.
• Timsort (Python’s sorted, Java’s Arrays.sort dla obiektów) - hybryda merge sort + insertion sort, wykrywa naturalnie posortowane runy. Lepszy dla danych częściowo uporządkowanych.

Skrótowo #

Merge sort: dziel na pół, sortuj rekurencyjnie, scalaj. O(n log n) gwarantowane, O(n) pamięci, stabilny. W praktyce quicksort / introsort wygrywają wewnątrz RAM, ale merge sort króluje w list, stable-sort, external sorting i parallel scenarios.