Hur väljer du mellan sorteringsalgoritmer?

Question

Accepted Answer

Valet av sortering beror på några egenskaper: **tidskomplexitet**, **stabilitet**, **minneanvändning på plats** och datakaraktären. Ingen enskild sortering vinner överallt.

## Nyckelegenskaper

- **Stabil:** lika element behåller sin ursprungliga relativa ordning (behövs för sortering på flera nycklar).
- **På plats:** använder O(1) eller O(log n) extra minne.
- **Adaptiv:** snabbare på nästan sorterad inmatning.

## Jämförelse

| Algoritm | Genomsn. tid | Värsta fall | Stabil | På plats |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Ja | Ja |
| Merge | O(n log n) | O(n log n) | Ja | Nej |
| Quick | O(n log n) | O(n²) | Nej | Ja |
| Heap | O(n log n) | O(n log n) | Nej | Ja |

## Vägledning

- **Liten / nästan sorterad** -> insertion sort.
- **Behöver stabilitet eller garanterad O(n log n)** -> merge sort.
- **Allmänt snabb i minnet, genomsnittshastighet viktigt** -> quicksort (randomiserad pivot).
- **Garanterad gräns + snålt 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
```

## Fallgropar

Implementera inte en sortering själv om du inte har en specifik anledning — bibliotekssorteringar (Timsort, introsort) är testade hybrider.

## Varför det spelar roll

Att matcha sorteringen till data och krav undviker både bortkastad tid och subtila buggar (som att förlora stabilitet).

Att förstå avvägningarna förklarar varför standardbibliotek valde hybrider som Timsort och introsort.

Denna komparativa bedömning — inte memorering av en algoritm — är vad verklig teknik och intervjuer belönar.

Algoritm	Genomsn. tid	Värsta fall	Stabil	På plats
Insertion	O(n²)	O(n²)	Ja	Ja
Merge	O(n log n)	O(n log n)	Ja	Nej
Quick	O(n log n)	O(n²)	Nej	Ja
Heap	O(n log n)	O(n log n)	Nej	Ja