codementor on Nostr: Learn: Sorting cheat sheet Costs, memory and stability of the common sorts, and what ...

Learn: Sorting cheat sheet

Costs, memory and stability of the common sorts, and what C#'s built-in sorts really do.

Read the full article:

quoting naddr1qq…gccd

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.Sort and List<T>.Sort are O(n log n) but not stable.
• LINQ OrderBy / ThenBy is 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

#tip · TIP-067