Hvordan velger du mellom sorteringsalgoritmer?

Question

Accepted Answer

Valg av sortering kommer ned til noen få egenskaper: **tidskompleksitet**, **stabilitet**, **in-place minne**, og datatypen. Ingen sortering vinner overalt.

## Viktige egenskaper

- **Stabil:** like elementer beholder sin originale relative rekkefølge (nødvendig for fler-nøkkel sortering).
- **In-place:** bruker O(1) eller O(log n) ekstra minne.
- **Adaptiv:** raskere på nesten sortert inndata.

## Sammenligning

| Algoritme | Gj.snitt tid | Verste fall | Stabil | In-place |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Ja | Ja |
| Merge | O(n log n) | O(n log n) | Ja | Nei |
| Quick | O(n log n) | O(n²) | Nei | Ja |
| Heap | O(n log n) | O(n log n) | Nei | Ja |

## Veiledning

- **Liten / nesten sortert** -> insertion sort.
- **Trenger stabilitet eller garantert O(n log n)** -> merge sort.
- **Generelt rask i-minne, gjennomsnittlig hastighet spiller rolle** -> quicksort (tilfeldig pivot).
- **Garantert grense + stramt minne** -> heap sort.

```python
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority)   # stable Timsort in Python
```

## Faller

Ikke lag din egen sort med mindre du har en spesifikk grunn — bibliotekssorter (Timsort, introsort) er hardtestet hybrider.

## Hvorfor det spiller rolle

Å tilpasse sorteringen til dataene og kravene unngår både sløsing med tid og subtile bugs (som å miste stabilitet).

Å forstå avveiningene forklarer hvorfor standardbiblioteker valgte hybrider som Timsort og introsort.

Denne komparative dommen — ikke memorering av én algoritme — er det som ekte ingeniørfag og intervjuer belønner.

Algoritme	Gj.snitt tid	Verste fall	Stabil	In-place
Insertion	O(n²)	O(n²)	Ja	Ja
Merge	O(n log n)	O(n log n)	Ja	Nei
Quick	O(n log n)	O(n²)	Nei	Ja
Heap	O(n log n)	O(n log n)	Nei	Ja