Array.Sort vs LINQ OrderBy, comparator rules, counting sort.

Sorting — Introsort, Stability, and When to Use Radix

Sorting falls into comparison-based (O(n log n) floor) and non-comparison (counting/radix, O(n+k)). .NET's Array.Sort uses introsort: quicksort with heapsort fallback for worst-case O(n log n). LINQ's OrderBy is stable (preserves equal keys' order). Comparators must be total orders (antisymmetry, transitivity, totality) — never return a - b for numerics. Radix sort excels when key range is small and relative to n.

Interactive Pipeline Flow

UnderstandImplementOptimise

📦 Input — array / collection

Input: any IEnumerable<T> or T[]. For large arrays, Array.Sort is fastest. For LINQ pipelines, OrderBy chains well.

Architecture Diagrams

Choose the right sort for your data characteristics.

Loading diagram...

Key Design Decisions

🚫Never return x - y in a comparator

Integer subtraction overflows. int.MinValue - 1 = int.MaxValue. Always use x.CompareTo(y) or Compare(x, y).

🔗Stable sort for multi-key sorting

Sort by secondary key first, then primary key with a stable sort. Equal-primary elements retain secondary order.

⚡Counting sort for small-range keys

Sort 10M records by month (1-12): counting sort is O(n+12). Array.Sort would be O(n log n) — 10x slower.

Discussion