CODEWITHSUNDEEP
sortingrecursionintrosort
Pkp
Pkp

Reputation: 969

Why is that in most online implementations, only single recursion is used in intro sort?

I was reading about intro sort. I understand most of it, but i fail to understand why most implementations tend to have one recursion for the quick sort part of it. Standard implementation of quick sort uses two recursions for quick sort.

Intro sort, main logic:
  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      while (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p, hi, depth_limit);
        hi=p;
      }
      insertionsort(a, lo, hi);
    }

Here I tried modifying the same to:

  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      if (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p + 1, hi, depth_limit);
        introsort_loop(a, lo , p-1 , depth_limit);
      }
      insertionsort(a, lo, hi);
    }

I did two modifications, one is i am now using two recursions now, secondly i am skipping the pivot element for recursions as it is already in the correct place.

Both with or without my modification the programs seems to run fine. But i wanted to know why they use single recursion in most implementations online.

Upvotes: 1

Views: 90

Answers (1)

templatetypedef
templatetypedef

Reputation: 372942

Many implementations of quicksort actually do use a single recursion and a while loop as a space-saving and time-saving trick.

Mathematically, the quicksort algorithm looks something like this:

 Partition elements.
 Quicksort(elements less than pivot)
 Quicksort(elements greater than pivot)

If you'll notice, there's no code that needs to get executed after the two recursive calls return.

Now, think about what will happen if you directly translate this pseudocode into real code. The original stack frame from when quicksort was initially called will stick around until both of the sub-calls to quicksort return. This means that the memory for the stack frame will persist until the entire algorithm finishes running, which takes up a lot of space. Additionally, if quicksort hits a degenerate case (not possible in introsort, but hang on for just a second), then you'll end up triggering a stack overflow.

A clever way to get around this is to realize that the above description of quicksort is actually amenable to tail call elimination. That is, instead of making a second call to quicksort, the implementation can just overwrite the parameters to the initial call, then sit in a while loop and reuse the space from the stack frame. This ends up significantly decreasing the space usage and eliminates a recursive call, which (while not prohibitively expensive) usually costs more than a while loop. Typically, an implementation will fire off a recursive call on the smaller of the two halves of the array and use the while loop to process the larger call, which guarantees space usage O(log n) even if you get a degenerate case.

The introsort implementation you've listed above looks like it's just adapting this trick to work for introsort rather than quicksort. Having one recursive call versus two doesn't mean that the algorithm isn't using quicksort, but just means that it's using a standard quicksort optimization technique.

Upvotes: 2

Related Questions