Sorting cheat sheet
Costs, memory and stability of the common sorts, and what C#'s built-in sorts really do.
Sorting cheat sheet
| Sort | Average | Worst | Extra memory | Stable? | Good for |
|---|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | yes | teaching, tiny arrays |
| Insertion | O(n²) | O(n²) | O(1) | yes | small or nearly sorted data |
| Merge | O(n log n) | O(n log n) | O(n) | yes | linked lists, stable sorting |
| Quick | O(n log n) | O(n²) | O(log n) | no | fast in practice on arrays |
| Heap | O(n log n) | O(n log n) | O(1) | no | guaranteed O(n log n) in place |
Stable means equal items keep their original order. It matters when you sort by one field after another (sort by name, then by age).
What C# does
Array.SortandList<T>.Sortare O(n log n) but not stable.- LINQ
OrderBy/ThenByis stable. - Both take a custom order: a comparison or a key.
var people = new List<(string Name, int Age)> { ("Ann", 30), ("Bob", 25), ("Cy", 30) };
var byAge = people.OrderBy(p => p.Age).Select(p => p.Name); // stable: Ann stays before Cy
Console.WriteLine(string.Join(" ", byAge));
int[] nums = { 3, 1, 2 };
Array.Sort(nums, (a, b) => b.CompareTo(a)); // custom order: largest first
Console.WriteLine(string.Join(" ", nums));
It prints Bob Ann Cy (Ann stays before Cy: stable), then 3 2 1 (largest first).
Interview tips
- Say the cost and whether it is stable.
- “Why is quick sort usually fast but O(n²) at worst?” Bad pivots split the array unevenly, for example always picking the first item of sorted data.
- Sorting first often makes the rest easy (two pointers, duplicates next to each other), but adds O(n log n).
Read more: https://www.geeksforgeeks.org/dsa/merge-sort/
#tip · TIP-067
Write a comment