Blog
Mert Özen's blog posts on software development, backend, frontend, and DevOps.
Quick Sort, Introsort and Counting/Radix Sort: How .NET's Array.Sort Sorts
Array.Sort uses introsort: quick sort, heapsort once the depth passes 2·log n, insertion sort for 16 elements or fewer; that is why a textbook quick sort with a last-element pivot becomes 749 times slower on 10,000 sorted elements while Array.Sort is unaffected. We cover Lomuto and Hoare partition, median-of-three, the Ω(n log n) lower bound, counting and radix sort that beat Array.Sort 11–12 times, and the a - b comparer trap, with tests.
Sorting Algorithms 1: Insertion Sort, Merge Sort and Stability
Array.Sort is not stable: sorting 200 date-ordered orders by customer scrambles each customer's dates, while merge sort and LINQ OrderBy keep them. We cover insertion sort (6 times faster than Array.Sort on 10,000 nearly sorted elements), top-down and bottom-up merge sort, the idea of external merge sort and stability, with xUnit tests and BenchmarkDotNet measurements.
Filtering and Sorting with LINQ: Where, OrderBy, ThenBy and Reverse
Where and its index overload, why a second OrderBy wipes out the first, multi-key sorting with ThenBy, stable OrderBy versus unstable List.Sort, culture-sensitive string ordering, and how Reverse differs from OrderByDescending.
Sorted Collections in C#: SortedList, SortedDictionary, SortedSet and IComparer
A book silently lost from a SortedSet when the comparer returns zero, and the tie-breaking second criterion. SortedDictionary on a red-black tree, SortedList with two sorted arrays and when to pick which; Min, Max and the live GetViewBetween on SortedSet; IComparer, culture-sensitive string order and broken comparer traps.