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?

trincot · Accepted Answer · 2024-04-01 07:25:48Z

1

Two things:

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.

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.

edited Apr 1, 2024 at 7:25

answered Mar 31, 2024 at 14:20

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

rcgldr Over a year ago

The recursive call on the the right partition occurs before the loop back to take care of the left partition.

Learner Over a year ago

Thank you for your answer! I am just wondering why they use recursive approach? I am asking because I often heard and listened that recursion is less performant than iterative approach.

flackoverstow Over a year ago

Recursion is iteration is recursion anyway..?

trincot Over a year ago

Sorry, @flackoverstow, I don't understand what you want to say.

flackoverstow Over a year ago

Maybe that would help explain my point: an iterative approach using a stack and a recursive approach using the stack, are essentially no different.. The performance thus would essentially be no different; we aren't going to find that Sort() sped up 10x by switching away from the recursive approach employed

|

Collectives™ on Stack Overflow

Does Sort() method in C# use recursion?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related