Quicksort

  • Algorithms
  • Sorting
  • JavaScript
  • Interviews

If you've followed this blog then you'll know that in the last year I have written about The Quadratic Sorting Algorithms (Bubble Sort, Selection Sort, and Insertion Sort) and Merge Sort. This week I'm picking apart Quicksort, which is another sorting algorithm. I've been putting this post off for a long time. Speaking frankly, Quicksort is incredibly complicated. I don't want to scare anyone off, and this will be a long post, but I'm going to try really hard to break down the mechanics that make Quicksort work, how it achieves its efficiency, and offer an implementation of this sorting algorithm.

The How Does Quicksort Work and Quicksort Step By Step sections will detail at a high level the concepts for how data moves around into a sorted order within Quicksort. Understanding the concept of the Pivot is crucial, and these sections will demonstrate how the Pivot works.

Below that, I get into code implementations, first for the Pivot Helper Function and then the Quicksort Function itself. These two functions also come with lengthy, step by step examples. These sections will get very into the weeds, but I urge you to stick with them, as they'll expose you to some really important programming fundamentals, like swapping items in place and recursion.

Finally I round this post out with a discussion of the Big O of Quicksort, and how selecting a Pivot has big consequences on the efficiency of this sorting algorithm.

How Does Quicksort Work?

Quicksort works by selecting one element (called the "Pivot" -- I'll also often refer to it as the "Pivot Item") and then finding the index where the Pivot should end up in the final, sorted array (note: as always we will be working to sort items in ascending order, from lowest to highest). With that Pivot Item in place, we move all of the numbers that are lower than the Pivot to the left of the Pivot, and then all of the numbers that are greater than the Pivot to the right of the Pivot.

Knowing that the Pivot is in its correct place, we then work recursively on the left side of the original Pivot, finding a new Pivot Item in the values to the left, placing those numbers item by item, then to the right of the original Pivot. We drill down in this recursive fashion all the way through the array, and eventually we wind up with a sorted array.

I realize that this high level explanation might not make sense, so let's slow things down and break down each step of a Quicksort.

Quicksort Step by Step

Say we start with the following array of random numbers, and we are looking to sort them in ascending order using Quicksort:

Original Array:

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

First Pivot

  1. Find the first item that isn't in its final place and choose that as the Pivot. Since we're just starting out and nothing is located in its final place (as far as we know), we can just select the first item in the array. So in this case, 3 will be our Pivot Item. I will mark it with p below the list:
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
 p
  1. Our next step is to look for everything that is less than the Pivot Item (3). Again, with no items in place that we know of, we will look through the entire list. I will mark anything that is less than 3 with an l below the list. Here's an example:
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
 p                                 l
  1. As we are looking through the list, we will swap anything that is less than the Pivot Item (3) with the first item to the right of the Pivot Item that is greater than the Pivot Item. In this case, we are only swapping 44 and 2:
[3, 2, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 p  l
  1. With each item that is less than the Pivot Item now moved to the right of the Pivot Item, swap the Pivot Item with the right-most Less Than item. In this case, we are swapping 3 and 2:
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 l  p
  1. So we now know that 3 is in place. I will mark any items that are in place with an asterisk (*) below the list. We can move onto pivot everything to the left the First Pivot Item

End of First Pivot Result:

[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
    *

Second Pivot

  1. After our First Pivot is done, we start looking to the left of the First Pivot Item (3) and find the first item that isn't in its final place. This is what we will now use as our new Pivot Item. In this case, 2 is the Pivot Item (marked again with a p):
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 p  *
  1. Now we need to look for everything that is less than 2. We only need to look right-wards until we find an item that is in place (marked with *)
  • 2 can stay where it is
  • End at 3 (which is in place, marked by *)
  1. No swaps take place, so we know 2 is in place. I'll mark it with *

End of Second Pivot Result:

[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 *  *

Third Pivot

  1. Now that everything to the left of the First Pivot Item (3) is in place, we can start looking to the right of it. Once again we'll find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 38 is the Pivot Item (p)
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 *  *  p
  1. As we are looking through the list, we will swap anything that is less than the Pivot Item (38) with the first item to the right of the Pivot Item that is greater than the Pivot Item. Again I'll mark anything that is swapped/less than 38 with l
  • 5 stays where it is
  • 15 swaps with 47
  • 36 swaps with 47
  • 26 swaps with 47
  • 27 swaps with 47
  • 4 swaps with 47
  • 19 swaps with 44

This leaves us with the following:

[2, 3, 38, 5, 15, 36, 26, 27, 4, 19, 46, 47, 44, 50, 48]
 *  *  p   l  l   l   l   l   l  l
  1. With each item that is less than the Pivot Item now moved to the right of the Pivot Item, swap the Pivot Item with the right-most Less Than item. In this case, we are swapping 38 and 19:
[2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48]
 *  *  l   l  l   l   l   l   l  p
  1. We now know that 38 is in place (again, marked with *). We can move onto pivot everything to the left the Third Pivot Item

End of Third Pivot Result:

[2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48]
 *  *                            *

Fourth Pivot

  1. Looking to the left of the Third Pivot Item (38), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 19 is the Pivot Item (p)
[2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48]
 *  *  p                         *
  1. Look for everything that is less than 19 (l). We only need to look right-wards until we find an item that is in place (*). Swap anything that is less than 19 with the first item to the right of the Pivot Item that is greater than 19
  • 5 stays where it is
  • 15 stays where it is
  • 4 swaps with 36

This leaves us with the following:

[2, 3, 19, 5, 15, 4, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  p   l  l   l              *
  1. With each item that is less than the Pivot Item now moved to the right of the Pivot Item, swap the Pivot Item with the right-most Less Than item. In this case, we are swapping 19 and 4:
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  l  l  l   p               *
  1. We now know that 19 is in place (*). We can move onto pivot everything to the left the Fourth Pivot Item

End of Fourth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *            *               *

Fifth Pivot

  1. Looking to the left of the Fourth Pivot Item (19), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 4 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  p         *               *
  1. Look for everything that is less than 4 (l). We only need to look right-wards until we find an item that is in place (*)
  • 5 and 15 can stay where they are
  • End at 19 (in place - *)
  1. No swaps take place, so we know 4 is in place (*)

End of Fifth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *         *               *

Sixth Pivot

  1. Looking to the right of the Fifth Pivot Item (4), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 5 is the Pivot (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  p      *               *
  1. Look for everything that is less than 5 (l). We only need to look right-wards until we find an item that is in place (*)
  • 15 can stay where it is
  • End at 19 (in place - *)
  1. No swaps take place, so we know 5 is in place (*)

End of Sixth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *      *               *

Seventh Pivot

Looking to the right of the Sixth Pivot Item (5), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 15 is the Pivot Item (p)

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  p   *               *
  1. Look for everything that is less than 15 (l). We only need to look right-wards until we find an item that is in place (*)
  • We immediately hit 19, which is in place (*)
  1. No swaps take place, so we know 15 is in place (*)

End of Seventh Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *               *

Eighth Pivot

  1. Looking to the right of the Third Pivot Item (19), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 26 is the Pivot (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   p           *
  1. Look for everything that is less than 26 (l). We only need to look right-wards until we find an item that is in place (*)
  • 27 and 36 can stay where they are
  • End at 38 (in place - *)
  1. No swaps take place, so we know 26 is in place (*)

End of Eighth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *           *

Ninth Pivot

  1. Looking to the right of the Eighth Pivot Item (26), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 27 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   p       *
  1. Look for everything that is less than 27 (l). We only need to look right-wards until we find an item that is in place (*)
  • 36 can stay where it is
  • End at 38 (in place - *)
  1. No swaps take place, so we know 27 is in place (*)

End of Ninth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   *       *

Tenth Pivot

  1. Looking to the right of the Ninth Pivot Item (27), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 36 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   *   p   *
  1. Look for everything that is less than 36 (l). We only need to look right-wards until we find an item that is in place (*)
  • We immediately hit 38, which is in place (*)
  1. No swaps take place, so we know 36 is in place (*)

End of Tenth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   *   *   *

Eleventh Pivot

  1. Looking to the right of the Third Pivot Item (38), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 46 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   *   *   *   p
  1. Look for everything that is less than 46 (l). We would stop looking right-wards if we hit any items that are in place, but in this case there are none, so we look through the rest of the list. Swap anything that is less than 46 with the first item to the right of the Pivot that is greater than 46
  • 44 swaps with 47
  • 50 and 48 can stay where they are
  • End at the end of the list

This leaves us with the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   p   l
  1. With each item that is less than the Pivot Item now moved to the right of the Pivot Item, swap the Pivot Item with the right-most Less Than item. In this case, we are swapping 46 and 44:
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   l   p
  1. We now know that 46 is in place (*). We can move onto pivot everything to the left the 46

End of Eleventh Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *       *

Twelfth Pivot

  1. Looking to the left of the Eleventh Pivot Item (46), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 44 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   p   *
  1. Look for everything that is less than 44 (l). We only need to look right-wards until we find an item that is in place (*)
  • We immediately hit 46, which is in place (*)
  1. No swaps take place, so we know 44 is in place (*)

End of Twelfth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *

Thirteenth Pivot

  1. Looking to the right of the Eleventh Pivot Item (46), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 47 is the Pivot (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *   p
  1. Look for everything that is less than 47 (l). We would stop looking right-wards if we hit any items that are in place, but in this case there are none, so we look through the rest of the list
  • 50 and 48 can stay where they are, which brings us to the end of the list
  1. No swaps take place, so we know 47 is in place (*)

End of Thirteenth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *   *

Fourteenth Pivot

  1. Looking to the right of the Thirteenth Pivot Item (47), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 50 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *   *   p
  1. Look for everything that is less than 50 (l). We would stop looking right-wards if we hit any items that are in place, but in this case there are none, so we look through the rest of the list
  • 48 stays in place; it is less than 50 but it's already directly to the right of 50

This leaves us with the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *   *   p   l
  1. With each item that is less than the Pivot Item now moved to the right of the Pivot Item, swap the Pivot Item with the right-most Less Than item. In this case, we are swapping 50 and 48:
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
 *  *  *  *  *   *   *   *   *   *   *   *   *   l   p
  1. We now know that 50 is in place (*). We can move onto pivot everything to the left the Pivot

End of Fourteenth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
 *  *  *  *  *   *   *   *   *   *   *   *   *       *

Fifteenth Pivot

  1. Looking to the left of the Fourteenth Pivot Item (50), find the first item that isn't in its final place and choose that as the new Pivot Item. In this case, 48 is the Pivot Item (p)
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
 *  *  *  *  *   *   *   *   *   *   *   *   *   p   *
  1. Look for everything that is less than 48 (l). We only need to look right-wards until we find an item that is in place (*)
  • We immediately hit 50, which is in place (*)
  1. No swaps take place, so we know 48 is in place (*)

End of Fifteenth Pivot Result:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
 *  *  *  *  *   *   *   *   *   *   *   *   *   *   *

End of Pivots

So after 15 pivot operations, we have a sorted array of numbers that can get returned. This was kind of painstaking to write out in this fashion, but hopefully it made the pattern clear for how Pivots work in Quicksort.

Pivot Helper Function

In order to implement Merge Sort, it's useful to first implement a function responsible for arranging elements in an array on either side of the Pivot.

Given an array, this helper function should designate an element as the Pivot. It should then rearrange elements in the array so that all values less than the Pivot are moved to the left of the Pivot, and all values greater than the Pivot are moved to the right of the Pivot. Note: the order of elements on either side of the Pivot doesn't matter!

The helper should do this in place, i.e. it should not create a new array. When complete, the helper should return the index of the Pivot.

Picking a Pivot

As a quick note, the runtime of Quicksort depends on how one selects the Pivot. Ideally, the Pivot should be chosen so that it's roughly the median value in the data set you're sorting. For simplicity, we'll always choose the Pivot to be the first element, but there are consequences in doing so (this will be discussed in the Big O section of this post).

Pivot Implementation

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };


  let pivotItem = arr[start];
  let swapIndex = start;


  for (let i = start + 1; i < arr.length; i++) {
    if (pivotItem > arr[i]) {
      swapIndex++;
      swap(arr, swapIndex, i);
    }
  }
  swap(arr, start, swapIndex);
  return swapIndex;
}

Here is our pivot function definition. It takes three parameters:

  1. An array, arr
  2. A start index, start; default value is 0
  3. An end index, end; default value is arr.length - 1

The first thing we have within the function block is a helper function called swap. This function has three parameters:

  1. An array, arr
  2. An index, index1
  3. Another index, index2

This swap function simply switches items at the two indexes in the array it is given. For example, swap([1, 2, 3], 0, 2) would return the array as [3, 2, 1].

Below that, we are defining a variable named pivotItem and assigning it the value of the first item in arr.

Then we define a variable named swapIndex. This will keep track of the index within arr where the pivotItem element ultimately ends up, but we'll start it at 0 (start's default value) for now.

Now we start a for loop. This will loop up from the second item in the array through the end of the array -- we do this because the first item is our Pivot Item.

Within the loop block, we compare pivotItem to the arr item we're looking at on that iteration of the loop. If the arr item is less than the pivotItem, then we increment swapIndex by 1, then swap the arr item from its current location to arr[swapIndex], switching spots with the value that was previously at swapIndex. In the long example above, this is the step where we move items that are less than the Pivot Item directly to the right of the Pivot Item, switching with items that are greater than the Pivot Item.

After the loop stops running, we simply need to take the final swapIndex item and switch it with the item at index start, in essence switching the pivotItem with the last item to its immediate right that is less than the pivotItem.

With that step done, everything to the left of the pivotItem is less than the pivotItem, and everything to the right of the pivotItem is greater than the pivotItem.

Example: Pivoting in Action

With the code written out and explained above, let's break it down with a concrete example.

Let's say this is our initial function call:

pivot([4, 8, 2, 1, 5, 7, 6, 3]);

Initial Definitions

So starting out, here are our variables and their values:

  • arr: [4, 8, 2, 1, 5, 7, 6, 3]
  • pivotItem: 4 (selected as the first item in arr)
  • swapIndex: 0

First Iteration

On the first iteration of the loop, i is 1 and we are comparing 4 and 8. 8 is greater than 4, so nothing happens except i increments by 1.

  • arr: [4, 8, 2, 1, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 0

Second Iteration

On the second iteration of the loop, i is 2 and we are comparing 4 and 2. 2 is less than 4, so swapIndex gets incremented by 1 and arr[2] gets swapped with arr[1].

  • arr: [4, 2, 8, 1, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 1

Third Iteration

On the third iteration of the loop, i is 3 and we are comparing 4 and 1. 1 is less than 4, so swapIndex gets incremented by 1 and arr[3] get swapped with arr[2].

  • arr: [4, 2, 1, 8, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 2

Fourth Iteration

On the fourth iteration of the loop, i is 4 and we are comparing 4 and 5. 5 is greater than 4, so nothing happens except i increments by 1.

  • arr: [4, 2, 1, 8, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 2

Fifth Iteration

On the fifth iteration of the loop, i is 5 and we are comparing 4 and 7. 7 is greater than 4, so nothing happens except i increments by 1.

  • arr: [4, 2, 1, 8, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 2

Sixth Iteration

On the sixth iteration of the loop, i is 6 and we are comparing 4 and 6. 6 is greater than 4, so nothing happens except i increments by 1.

  • arr: [4, 2, 1, 8, 5, 7, 6, 3]
  • pivotItem: 4
  • swapIndex: 2

Seventh Iteration

On the seventh and final iteration of the loop, i is 7 and we are comparing 4 and 3. 3 is less than 4, so swapIndex gets incremented by 1 and arr[7] gets swapped with arr[3].

  • arr: [4, 2, 1, 3, 5, 7, 6, 8]
  • pivotItem: 4
  • swapIndex: 3

Final Swap

Now that the loop has stopped running, everything that is less than pivotItem has been moved immediately to the right of pivotItem. The last item that is less than pivotItem, 3, is located at index 3, which we have kept track of with the swapIndex variable. At this point all we need to do is swap the pivotItem from its place at index 0 (which the start variable keeps track of). So all we have to do is run swap(arr, start, swapIndex).

This gives us the following arr:

[3, 2, 1, 4, 5, 7, 6, 8]

So now everything to the left of the pivotItem is less than the pivotItem, and everything to the right of the pivotItem is greater than the pivotItem, and the pivotItem is in its final spot in the array, at index swapIndex (4). All we need to do is return the value of swapIndex, which will help the rest of our Quicksort function run.

Quicksort Implementation

Now it's time to write our actual quickSort function. Here is the full, final implementation, including the pivot function from above:

function pivot(arr, start = 0, end = arr.length - 1) {
  const swap = (arr, index1, index2) => {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  };


  let pivotItem = arr[start];
  let swapIndex = start;


  for (let i = start + 1; i < arr.length; i++) {
    if (pivotItem > arr[i]) {
      swapIndex++;
      swap(arr, swapIndex, i);
    }
  }
  swap(arr, start, swapIndex);
  return swapIndex;
}


function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

Our quickSort function definition will accept three parameters:

  1. The array we're going to sort, arr
  2. A left index, left; default value is 0
  3. A right index, right; default value is arr.length - 1

This function will work recursively. It will initially set the pivot point as the first item in the array, and then once that item is in place, it will call itself again on various smaller sections of the array. We saw this process play out numerous times waaaay above (for a good example, look at Fourth Pivot). This function will repeatedly call itself with new left and right values until it gets down to individual items within the array, at which point it will know that items are sorted in their correct place. The base case for the recursive calls is when the value of left is either the same as or greater than the value of right. This occurs when we are looking at an individual element within the array that is in its final place in the array.

Example: Quicksort

With our Quicksort implementation code in hand, let's circle all the way back to our original example array, and step through it. Because we're calling quickSort recursively, this is going to get a little bit messy and probably hard to follow, so hopefully It'll make sense. That said, the spirit of this blog is to dive deep and (sometimes painstakingly) break difficult concepts and code down into their smallest, most digestible parts. So that's what we're going to do.

Let's call the function with the following array argument:

quickSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);

First quickSort Function Call

  • arr: [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  • left: 0 (default value given in function definition)
  • right: 14 (from arr.length - 1, or the default value given in function definition)

left is less than right, so we call pivot([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48], 0, 14).

First pivot Function Call

pivot([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48], 0, 14);
  • arr: [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
  • start: 0
  • end: 14

This function call pivots 3 into place, rearranging arr into the following:

[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
    *

It also returns swapIndex as 1.

Back in the First quickSort Function Call, the swapIndex value (1) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[1].

Second quickSort Function Call

quickSort([2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48], 0, 0);
  • arr is [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
  • pivotIndex is 1
  • left is 0
  • right is 0 (pivotIndex - 1)

Because left and right are the same, we simply return arr and move onto the second recursive quickSort function call within the first quickSort function call. At this point, everything to the left of 3 is in place, so we move onto the right side of 3.

Returned arr:

[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
 *  *

Third quickSort Function Call

quickSort([2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48], 2, 14);
  • arr is [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
  • pivotIndex is 1
  • left is 2 (pivotIndex + 1)
  • right is 14

left is less than right, so we call pivot([2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48], 2, 14).

Second pivot Function Call

pivot([2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48], 2, 14);

This function call pivots 38 into place, rearranging arr into the following:

[2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48]
 *  *                            *

It also returns swapIndex as 9.

Back in the Third quickSort Function Call, the swapIndex value (9) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[9].

Fourth quickSort Function Call

quickSort([2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48], 2, 8);
  • arr is [2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48]
  • pivotIndex is 9
  • left is 2
  • right is 8 (pivotIndex - 1)

left is less than right, so we call pivot([2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48], 2, 8).

Third pivot Function Call

pivot([2, 3, 19, 5, 15, 36, 26, 27, 4, 38, 46, 47, 44, 50, 48], 2, 8);

This function call pivots 19 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *            *               *

It also returns swapIndex as 5.

Back in the Fourth quickSort Function Call, the swapIndex value (5) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[5].

Fifth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 2, 4);
  • arr is [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex is 5
  • left is 2
  • right is 4 (pivotIndex - 1)

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 2, 4).

Fourth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 2, 4);

This function call pivots 4 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *         *               *

No swaps take place, and swapIndex gets returned as 2.

Back in the Fifth quickSort Function Call, the swapIndex value (2) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[2].

Sixth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 2, 1);
  • arr is [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex is 2
  • left is 2
  • right is 1 (pivotIndex - 1)

Because left is greater than right, we simply return arr and move onto the second recursive quickSort function call within the Fifth quickSort function call. At this point, everything to the left of 4 is in place, so we move onto the right side of 4.

These are the items we currently have in place:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *         *               *

Seventh quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 3, 4);
  • arr is [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex is 2
  • left is 3 (pivotIndex + 1)
  • right is 4

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 3, 4).

Fifth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 3, 4);

This function call pivots 5 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *      *               *

No swaps take place, and swapIndex gets returned as 3.

Back in the Seventh quickSort Function Call, the swapIndex value (3) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[3].

Eighth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 3, 2);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 3
  • left: 3
  • right: 2 (pivotIndex - 1)

Because left is greater than right, we simply return arr and move onto the second recursive quickSort function call within the Seventh quickSort function call. At this point, everything to the left of 5 is in place, so we move onto the right side of 5.

Ninth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 4, 4);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 3
  • left: 4 (pivotIndex + 1)
  • right: 4

Because left and right are the same, we simply return arr and move onto the second recursive quickSort function call within the Fifth quickSort Function Call. At this point, everything to the left of 19 is in place, so we move onto the right side of 19.

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *               *

Tenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 6, 8);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 5
  • left: 6 (pivotIndex + 1)
  • right: 8

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 6, 8).

Sixth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 6, 8);

This function call pivots 26 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *           *

No swaps take place, and swapIndex gets returned as 6.

Back in the Tenth quickSort Function Call, the swapIndex value (6) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[6].

Eleventh quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 6, 5);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 6
  • left: 6
  • right: 5 (pivotIndex - 1)

Because left is greater than right, we simply return arr and move onto the second recursive quickSort function call within the Ninth quickSort function call. At this point, everything to the left of 26 is in place, so we move onto the right side of 26.

These are the items we currently have in place:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *           *

Twelfth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 7, 8);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 6
  • left: 7 (pivotIndex + 1)
  • right: 8

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 7, 8).

Seventh pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 7, 8);

This function call pivots 27 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
 *  *  *  *  *   *   *   *       *

No swaps take place, and swapIndex gets returned as 7.

Back in the Twelfth quickSort Function Call, the swapIndex value (7) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[7].

Thirteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 7, 6);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 7
  • left: 7
  • right: 6 (pivotIndex - 1)

Because left is greater than right, we simply return arr and move onto the second recursive quickSort function call within the Twelfth quickSort function call. At this point, everything to the left of 27 is in place, so we move onto the right side of 27.

Fourteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 8, 8);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 7
  • left: 8 (pivotIndex + 1)
  • right: 8

Because left and right are the same, we simply return arr and move onto the second recursive quickSort function call within the Third quickSort Function Call. At this point, everything to the left of 38 is in place, so we move onto the right side of 38.

Fifteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 10, 14);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48]
  • pivotIndex: 9
  • left: 10
  • right: 14

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 10, 14).

Eighth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 47, 44, 50, 48], 10, 14);

This function call pivots 46 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *       *

It also returns swapIndex as 11.

Back in the Fifteenth quickSort Function Call, the swapIndex value (11) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[11].

Sixteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 10, 10);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
  • pivotIndex: 11
  • left: 10
  • right: 10 (pivotIndex - 1)

Because left and right are the same, we simply return arr and move onto the second recursive quickSort function call within the Fifteenth quickSort Function Call. At this point, everything to the left of 46 is in place, so we move onto the right side of 46.

Seventeenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 12, 14);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
  • pivotIndex: 11
  • left: 12
  • right: 14 (pivotIndex - 1)

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 12, 14).

Ninth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 12, 14);

This function call pivots 47 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
 *  *  *  *  *   *   *   *   *   *   *   *   *

No swaps take place, and swapIndex gets returned as 12.

Back in the Seventeenth quickSort Function Call, the swapIndex value (12) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[12].

Eighteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 12, 11);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
  • pivotIndex: 12
  • left: 12
  • right: 11 (pivotIndex - 1)

Because left is greater than right, we simply return arr and move onto the second recursive quickSort function call within the Seventeenth quickSort function call. At this point, everything to the left of 47 is in place, so we move onto the right side of 47.

Nineteenth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 13, 14);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
  • pivotIndex: 12
  • left: 13 (pivotIndex + 1)
  • right: 14`

left is less than right, so we call pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 13, 14).

Tenth pivot Function Call

pivot([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48], 13, 14);

This function call pivots 50 into place, rearranging arr into the following:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
 *  *  *  *  *   *   *   *   *   *   *   *   *       *

It also returns swapIndex as 14.

Back in the Nineteenth quickSort Function Call, the swapIndex value (14) gets stored into the pivotIndex variable. We now recursively call quickSort again, this time to pivot items to the left of arr[14].

Twentieth quickSort Function Call

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50], 13, 14);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  • pivotIndex: 14`
  • left: 13
  • right: 13 (pivotIndex - 1)

Because left and right are the same, we simply return arr and move onto the second recursive quickSort function call within the...Seventeenth?? (I have lost track at this point) quickSort Function Call. At this point, everything to the left of 50 is in place, so we move onto the right side of 50.

quickSort([2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50], 15, 14);
  • arr: [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
  • pivotIndex: 14
  • left: 15 (pivotIndex + 1)
  • right: 14

Because left is greater than right, we simply return arr. At this point we've reached the end of the array, and we're something like six recursive quickSort function calls deep into our stack (hard to keep track, but Google Developer Tools helps!). arr is [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50], in its final, sorted order. arr gets returned all the way up the recursive call stack.

We wind up back at the very first quickSort Function Call, and [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] gets returned. arr has been Quicksorted into order.

Quicksort Big O

ComplexityBig O
Time (Best)O(n log n)
Time (Average)O(n log n)
Time (Worst)O(n²)
SpaceO(log n)

Like with Merge Sort, as the size of the data grows, we have to make O(log n) decompositions. We also have to make O(n) comparisons per decomposition. This gives us O(n log n) Best and average times for sorting using Quicksort.

Let's discuss the worst case scenario. In our example we have taken the first item as our pivot. That can be problematic if our data is almost sorted. If that's the case, each decomposition is only one item that we're pivoting on. Worst case is O(n) decompositions and O(n) comparisons for each of those decompositions. This results in quadratic time O(n²). We get this when the pivot is always the minimum or always the maximum.

Space (memory) complexity also relies on the number of recursive function calls. Each recursive quickSort call must store a constant amount of information for each nested recursive call. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space.