Array.Sort vs List.Sort Differences in C

Developers frequently wonder whether Array.Sort and List<T>.Sort rely on different sorting algorithms in C# to achieve optimal performance. In modern .NET implementations, both methods use the exact same underlying algorithm: IntroSort (Introspective Sort). This article breaks down how this algorithm works, how List<T>.Sort is connected to Array.Sort, and the few practical distinctions between using the two APIs.

The Underlying Algorithm: IntroSort

Both Array.Sort and List<T>.Sort utilize IntroSort, a hybrid comparison-based sorting algorithm. IntroSort dynamically selects among three algorithms based on the state of the data:

  1. QuickSort: The algorithm begins with a standard dual-pivot or median-of-three QuickSort, which provides fast average-case performance of \(O(n \log n)\).
  2. HeapSort: If the recursion depth exceeds a threshold (typically \(2 \times \log_2(n)\)), IntroSort switches to HeapSort. This avoids QuickSort's worst-case time complexity of \(O(n^2)\) and guarantees an upper bound of \(O(n \log n)\).
  3. InsertionSort: When a partition becomes small (typically 16 elements or fewer), the algorithm switches to InsertionSort, which runs faster on small arrays due to minimal overhead and high cache locality.

How List.Sort Relies on Array.Sort

List<T> in .NET is a wrapper around an internal array named _items. When you call List<T>.Sort(), the runtime does not execute a distinct sorting algorithm. Instead, it directly invokes Array.Sort:

// Internal .NET implementation detail of List<T>.Sort
Array.Sort(this._items, 0, this._size, comparer);

Because of this direct delegation, List<T>.Sort and Array.Sort<T> share identical algorithmic execution paths, theoretical time complexities, and memory usage characteristics.

Key Practical Differences

While the algorithms are identical, there are operational differences to consider:

  • API Design: Array.Sort is a static method on the System.Array class, requiring the target array to be passed as an argument. List<T>.Sort is an instance method that modifies the list directly.
  • Non-Generic Overloads: Array.Sort provides legacy non-generic overloads that operate on weakly typed System.Array references. These overloads require runtime type checking and boxing/unboxing for value types, making them significantly slower than the generic Array.Sort<T> or List<T>.Sort.
  • Span Support: Modern .NET provides MemoryExtensions.Sort, allowing you to sort Span<T> and ReadOnlySpan<T> using the same IntroSort engine. This offers zero-allocation sorting over subsets of arrays without needing to pass separate index and length parameters.

Stability and Alternatives

Neither Array.Sort nor List<T>.Sort is a stable sort. If two elements have equal keys, their relative order is not guaranteed to be preserved after sorting.

If stability is required, developers must use LINQ's OrderBy or OrderByDescending methods instead. Note that LINQ sorting performs an out-of-place, stable sort that allocates additional memory and yields \(O(n \log n)\) performance, trading execution speed and memory efficiency for order preservation.