This article is Part 1 in a 5-Part Series.

Welcome to my new series about Sorting and .NET Internals. It has started as a simple question Hey, I wonder how sorting implementation looks like in .NET?. This was planned as one one blog post, quick wrap up and another topic. But when I started reading, I just couldn’t stop asking question Why?. This series is a journey through the code starting with List.Sort() and ending at IntroSort algorithm.

To make it more manageable, I divided this work to two chapters:

  • Chapter I - .NET internals - from List<T>.Sort() to TrySZSort
    • A journey through the code. Starting with List<T>.Sort() and ending on assembly code level. If you are interested in how .NET and CLR work internally or what FCall, QCall, P/Invoke, marshalling is. This is must have chapter for you. If you are not interested in .NET internals, you can jump straight ahead to Chapter II.
  • Chapter II - Sorting in the real world - IntroSort
    • Going to the details of sorting in the real world. Focusing on Quicksort but also discussing other algorithms pros/cons and trade-offs. This will serve as a great introduciton to explanation why .NET uses IntroSort. We are also going to discuss .NET implementation of IntroSort.

Today there is only first part available. Next parts publication is planned to happen in 1-2 weeks time.

Chapter I - .NET Internals:

Chapter II - Sorting in the real world - IntoSort:

  • Basics Of Quicksort
  • Overview of search algorithms - strength and weaknesses
  • IntroSort
  • CLR implementation