Hur fungerar merge sort?

Question

Accepted Answer

**Merge sort** är en **dela-och-härska**, **stabil** sortering som körs i garanterad **O(n log n)** tid. Den delar upp arrayen på mitten, sorterar varje halva rekursivt och slår sedan ihop de två sorterade halvorna.

## Idén

Ett enda element är redan sorterat (basfall). Sammanslagning av två sorterade listor är linjär, och vi gör log n nivåer av sammanslagning.

## Exempel

```python
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]
```

## Komplexitet

- **Tid:** O(n log n) i *alla* fall (bästa, genomsnittlig, värsta).
- **Utrymme:** O(n) för sammanslagningsbuffrarna (inte på plats).

## När du ska använda / fallgropar

Ideal när du behöver **stabilitet** eller garanterad O(n log n), och för **länkade listor** och **extern sortering** av enorma filer. Det extra O(n) minnet är dess huvudsakliga nackdel.

## Varför det spelar roll

Merge sort garanterar O(n log n) oavsett input, till skillnad från quicksorts O(n²) värsta fall.

Dens stabilitet bevarar den relativa ordningen av lika nycklar, vilket spelar roll för flernyckelsortering.

Sammanslagningssteget är en återanvändbar primitiv, och dela-och-härska-strukturen är en mall som du kommer att återanvända överallt.