How do you choose between sorting algorithms?

Question

Accepted Answer

Choosing a sort comes down to a few properties: **time complexity**, **stability**, **in-place memory use**, and the nature of the data. No single sort wins everywhere.

## Key properties

- **Stable:** equal elements keep their original relative order (needed for multi-key sorts).
- **In-place:** uses O(1) or O(log n) extra memory.
- **Adaptive:** faster on nearly-sorted input.

## Comparison

| Algorithm | Avg time | Worst | Stable | In-place |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Yes | Yes |
| Merge | O(n log n) | O(n log n) | Yes | No |
| Quick | O(n log n) | O(n²) | No | Yes |
| Heap | O(n log n) | O(n log n) | No | Yes |

## Guidance

- **Small / nearly sorted** -> insertion sort.
- **Need stability or guaranteed O(n log n)** -> merge sort.
- **General fast in-memory, average speed matters** -> quicksort (randomized pivot).
- **Guaranteed bound + tight memory** -> heap sort.

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

## Pitfalls

Don't hand-roll a sort unless you have a specific reason — library sorts (Timsort, introsort) are battle-tested hybrids.

## Why it matters

Matching the sort to the data and requirements avoids both wasted time and subtle bugs (like losing stability).

Understanding the trade-offs explains why standard libraries chose hybrids like Timsort and introsort.

This comparative judgment — not memorizing one algorithm — is what real engineering and interviews reward.

Algorithm	Avg time	Worst	Stable	In-place
Insertion	O(n²)	O(n²)	Yes	Yes
Merge	O(n log n)	O(n log n)	Yes	No
Quick	O(n log n)	O(n²)	No	Yes
Heap	O(n log n)	O(n log n)	No	Yes