Quick Sort

Say you have a big pile of exam papers to sort by marks. Doing it one swap at a time is slow. So you do something smarter. You pick one paper. Then you push every lower-mark paper to its left and every higher-mark paper to its right. Now that one paper is already in its final spot. After that you do the same trick on the left pile and on the right pile.

That is exactly what Quick Sort does. Quick Sort is a sorting method that picks one element, called the pivot, and splits the array around it. The smaller items move to its left and the bigger items move to its right. Then it sorts each side the same way.

🎯 What Problem Does It Solve?

Sorting by hand means comparing and swapping every pair. That takes a lot of work. The pain is all those repeated passes over the whole array.

Quick Sort cuts the work down. Each time it places the pivot in its correct final position. Then it only has to deal with two smaller pieces. So the big problem keeps breaking into smaller and smaller problems. This goes on until each piece is tiny and already sorted.

This idea of breaking a problem into smaller copies of itself is called divide and conquer. You divide the array, solve the small parts, and the whole thing ends up sorted.

🧩 The Pivot and the Partition

The heart of Quick Sort is one move called partition. Partition means rearranging the array around a chosen pivot. Everything smaller sits before it and everything larger sits after it.

Here is the plan in plain words:

• Pick a pivot. We will use the last element. It is simple and works fine for learning.
• Walk through the rest of the array from left to right.
• Keep a marker for the boundary of the “smaller than pivot” zone.
• Every time you find an element smaller than the pivot, swap it into that zone and move the marker forward.
• At the end, swap the pivot into the spot right after the zone. Now the pivot is in its final place.

This style of partition uses the last element as the pivot and one marker to grow the smaller zone. It is called the Lomuto partition.

🔍 A Small Trace

Let us partition this array. The pivot is the last element, 4.

Array:  [7, 2, 9, 1, 4]
Pivot:  4  (the last element)

We use a marker i that sits just before the smaller zone. It starts at -1, since there are no smaller items yet. We scan with j from the first element up to the one before the pivot.

Let us follow the swaps step by step:

• Start: [7, 2, 9, 1, 4], marker i = -1.
• j = 0, value 7. Is 7 less than 4? No. Skip.
• j = 1, value 2. Is 2 less than 4? Yes. Move i to 0, then swap positions 0 and 1. The array becomes [2, 7, 9, 1, 4].
• j = 2, value 9. Less than 4? No. Skip.
• j = 3, value 1. Less than 4? Yes. Move i to 1, then swap positions 1 and 3. The array becomes [2, 1, 9, 7, 4].
• The scan is done. Now swap the pivot in the last spot with position i + 1, which is 2. The array becomes [2, 1, 4, 7, 9].

Now the pivot 4 is in its final position. Everything to its left is smaller and everything to its right is larger.

📝 Steps to Quick Sort an Array

Here is the full method, written as a recipe you can follow.

1. If the part you are looking at has one element or none, it is already sorted. Stop.
2. Run partition on the current part. This puts the pivot in its final position and gives you the pivot index.
3. Apply Quick Sort to the left part, from the start up to just before the pivot.
4. Apply Quick Sort to the right part, from just after the pivot to the end.
5. When all parts are done, the whole array is sorted.

Steps 3 and 4 call Quick Sort again on smaller pieces. A function that calls itself like this is called recursion.

💻 Quick Sort in 5 Languages

Below is Quick Sort with a Lomuto partition helper. The partition function does the rearranging and returns the pivot’s final index. The quickSort function calls itself on the left and right pieces.

#include <stdio.h>

// Swap two integers using pointers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Lomuto partition: pivot is the last element
int partition(int arr[], int low, int high) {
    int pivot = arr[high];      // chosen pivot
    int i = low - 1;            // boundary of the smaller zone

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {   // found a smaller element
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]); // put pivot in its final spot
    return i + 1;                  // pivot index
}

// Recursively sort the array
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);   // sort left part
        quickSort(arr, p + 1, high);  // sort right part
    }
}

int main() {
    int arr[] = {7, 2, 9, 1, 4};
    int n = 5;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

1 2 4 7 9

#include <iostream>
using namespace std;

// Lomuto partition: pivot is the last element
int partition(int arr[], int low, int high) {
    int pivot = arr[high];   // chosen pivot
    int i = low - 1;         // boundary of the smaller zone

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {   // found a smaller element
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // put pivot in its final spot
    return i + 1;                // pivot index
}

// Recursively sort the array
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int p = partition(arr, low, high);
        quickSort(arr, low, p - 1);   // sort left part
        quickSort(arr, p + 1, high);  // sort right part
    }
}

int main() {
    int arr[] = {7, 2, 9, 1, 4};
    int n = 5;

    quickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

1 2 4 7 9

public class QuickSort {

    // Swap two elements in the array
    static void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    // Lomuto partition: pivot is the last element
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];   // chosen pivot
        int i = low - 1;         // boundary of the smaller zone

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {   // found a smaller element
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);  // put pivot in its final spot
        return i + 1;            // pivot index
    }

    // Recursively sort the array
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);   // sort left part
            quickSort(arr, p + 1, high);  // sort right part
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 2, 9, 1, 4};

        quickSort(arr, 0, arr.length - 1);

        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

1 2 4 7 9

# Lomuto partition: pivot is the last element
def partition(arr, low, high):
    pivot = arr[high]      # chosen pivot
    i = low - 1            # boundary of the smaller zone

    for j in range(low, high):
        if arr[j] < pivot:                 # found a smaller element
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # swap into zone

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # place pivot
    return i + 1                                   # pivot index

# Recursively sort the array
def quick_sort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)   # sort left part
        quick_sort(arr, p + 1, high)  # sort right part

arr = [7, 2, 9, 1, 4]
quick_sort(arr, 0, len(arr) - 1)
print(arr)

[1, 2, 4, 7, 9]

// Lomuto partition: pivot is the last element
function partition(arr, low, high) {
  const pivot = arr[high]; // chosen pivot
  let i = low - 1;         // boundary of the smaller zone

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {  // found a smaller element
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swap into zone
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // place pivot
  return i + 1;                                      // pivot index
}

// Recursively sort the array
function quickSort(arr, low, high) {
  if (low < high) {
    const p = partition(arr, low, high);
    quickSort(arr, low, p - 1);  // sort left part
    quickSort(arr, p + 1, high); // sort right part
  }
}

const arr = [7, 2, 9, 1, 4];
quickSort(arr, 0, arr.length - 1);
console.log(arr.join(" "));

1 2 4 7 9

⏱️ How Fast Is It?

The speed of Quick Sort depends a lot on the pivot you pick. The very same algorithm can be fast or slow. It comes down to luck and to how you choose the pivot.

When the pivot lands near the middle each time, the array splits into two near-equal halves. That gives O(n log n) time, which is fast. This is the average case and the best case.

The bad case is when the pivot is always the smallest or the largest element. Then one side is empty and the other side holds everything. The array shrinks by just one each time, which gives O(n^2) time. This happens, for example, when you use the last-element pivot on an array that is already sorted.

Quick Sort sorts the array in place, so it does not need a second array. But recursion uses the call stack, and that needs about O(log n) space when the splits are balanced.

One more thing. Quick Sort is not stable. Stable means equal elements keep their original order. Quick Sort can swap equal elements past each other, so their order may change.

Here is the full picture.

⚠️ Common Mistakes

A few small slips trip up almost everyone the first time.

• Starting the marker i at low instead of low - 1. Then the very first smaller element lands in the wrong spot.
• Forgetting the final swap that places the pivot. Without it, the pivot never reaches its correct position.
• Recursing with the wrong bounds. The left call goes up to p - 1 and the right call starts at p + 1. If you include p again, it can loop forever.
• Always using the last element as the pivot on sorted data. That triggers the slow O(n^2) case. Pick a random pivot to stay safe.
• Missing the base case low < high. Without it the recursion never stops.

🧩 What You’ve Learned

• ✅ Quick Sort picks a pivot, partitions the array around it, then sorts the two sides.
• ✅ Partition pushes smaller elements left and larger ones right, then locks the pivot in its final place.
• ✅ The Lomuto partition uses the last element as pivot and one marker to grow the smaller zone.
• ✅ Quick Sort runs in O(n log n) on average but can drop to O(n^2) with bad pivots.
• ✅ It sorts in place, uses about O(log n) stack space, and is not stable.
• ✅ Picking the pivot well, with a random pivot or the median of three, keeps the slow case away.

🚀 What’s Next?

• Merge Sort
• Heap Sort