Quick Sort

Quick Sort is a sorting algorithm that is one of the earliest developed to have reached nlog(n) time while also being able to work in-place.

How Quick Sort works

Quick Sort first starts by picking a pivot. The pivot can be chosen from a specific point (beginning, middle or end) or though a random guess. It then traverses the array and compares every other item to the pivot. If it’s lower, it’s placed on the left; if it’s greater, it goes to the right.

After every item has been sorted compared to the pivot, we guarantee that all items to the left are lower than those on the right, so there is no need to inter-compare them. Instead, we run Quick Sort recursively on the left side and right side until we reach an array of size 1, which is where it returns.


Imagine we have this array:

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

We pick a random element as a pivot, say the number 4. Then we compare every number to 4, and place it to the left if it is lower or to the right if it is higher. Eventually, we’ll end up with this:

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

Now we know that 4 is in the correct position and everything to the left is lower and everything to the right is higher. Now we perform the Quick Sort algorithm again recursively on these two arrays:

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

And on and on until the recursive sizes reach size 1, which is in itself a sorted list.



Time complexity

Quick Sort uses comparisons and swaps to sort the array.


Comparions in Quick Sort follow a pattern bounded by O(nlog(n)), but it doesn’t follow that formula exactly. I tried adding 2n to it, but I have the feeling that it’s not quite right and might diverge at higher numbers


Swaps are similarly bounded, but with a lower coefficient.


This is how the comparisons and swaps are distributed for this sorting algorithm of size 100 for 100,000 sorts.

Mode: 622
Mean: 647
Std dev: 59
Max: 1098
Min: 505

Mode: 398
Mean: 425
Std dev: 61
Max: 901
Min: 253

Both of the distributions are fairly similar, they are a normal distribution that is skewed towards the side.

However what is most interesting about it is what the skews represent for what the best/worst situation that Quick Sort can find itself in.

Theoretically, the worst-case scenario for Quick Sort can end up being equivalent to Bubble Sort. This is because if the pivot you choose is either the maximum or minimum value, it essentially puts all the elements on just one side of the pivot which defeats the point of its divide-and-conquer technique.

The best-case scenario would involve every iteration have the algorithm split it right down the middle. Eventually you’ll get an outcome which is slightly better than the average, with a formula of nlog(n-1), but I could be wrong about that.

C code

void quick_sort(int *p, int len, int level, int pivot) {
	int i;		// Left side counter
	int r=0;	// Right (reverse) counter

	// Start going through the array upwards
	for (i=0; i<len-r;i++) {
		if (i < pivot) {
			// Picked from the left of the pivot
			if (is_less_than(p[i], p[pivot])) {
				// It's in the correct position, do nothing
			} else {
				// It needs to be shifted to the right
				swap(&p[i], &p[len-1-r]);
				// If we're swapping with the pivot, remember to change the pivot's location
				if (len-1-r == pivot) {
					pivot = i;
		} else if (i == pivot) {
			// Is the pivot, do nothing
		} else {
			// Picked from the right
			if (is_greater_than(p[i], p[pivot])) {
				// It's in the correct position, do nothing
			} else {
				// It needs to be shifted to the left, just before the pivot
				if (i > pivot+1) {
					// Swap with the one right after the pivot if it is too far away
					swap(&p[i], &p[pivot+1]);
				// It should be right after the pivot now, swap with the pivot
				swap(&p[pivot], &p[pivot+1]);
	// Call recursively
	// Left side
	if (pivot > 1) {
		quick_sort_recursive(p, pivot, level+1, rand() % pivot);
	// Right side
	if (len-pivot-1 > 1) {
		quick_sort_recursive(&p[pivot+1], len-pivot-1, level+1, rand() % (len-pivot-1));


Subscribe to the mailing list

Follow N64 Squid

  • RSS Feed
  • YouTube

Random featured posts