Does Sort() method in C# use recursion?

Question

I have read recently that C# uses Quicksort algorithm to sort an array. What I would like to know whether C# uses recursive approach or iterative approach?

What I have found is this link and it looks to me that they use iterative approach. I am just wondering whether it is true that C# uses iterative implementation of QuickSort algorithm?

Answer 1

Two things:

1. C# moved away from QuickSort to IntrospectiveSort, as also your link shows. You can see the comments and compatibility support at the Sort source code.

2. The code you refer to is recursive. Near the end of the loop is a recursive call:

   private void IntroSort(int lo, int hi, int depthLimit)
   {
       while (hi > lo)
       {
           int partitionSize = hi - lo + 1;
           if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
           {
               // ... 
               InsertionSort(lo, hi);
               return;
           }
           // ...
           int p = PickPivotAndPartition(lo, hi);
           IntroSort(p + 1, hi, depthLimit); // <--- recursive call
           hi = p - 1;
       }
   }
   

   The next iteration of the loop takes the left partition, and the recursive call takes the right partition.