Quick Sort in C, C++, Java and Python: Full Guide

Quick sort divides an array around a pivot element, then recursively sorts the two resulting halves, achieving O(n log n) average time while sorting in place.

This article covers pivot selection strategies (last, first, random, median-of-three), the Lomuto partition scheme with a full step-by-step trace on a six-element array, and working implementations in C, C++, Java, and Python. The time and space complexity table and a quick sort vs merge sort comparison close the article.

What Quick Sort Does

The algorithm cycles through three steps on every subarray it receives:

• Choose a pivot from the current subarray.
• Partition the subarray so every element smaller than the pivot sits to its left and every element larger sits to its right. The pivot lands at its exact final sorted position.
• Recurse on the left partition (elements smaller than pivot) and the right partition (elements larger than pivot).

The base case is a subarray of length 0 or 1, which needs no work. Recursion stops naturally.

Two properties follow directly. First, no element ever crosses the pivot again after partition. Second, the algorithm is in-place: it rearranges elements within the original array using only swaps. The only extra memory is the call stack, which holds one stack frame per recursion level. That averages O(log n) frames when each partition splits the subarray roughly in half.

Pivot Selection Strategies

Pivot choice determines whether the algorithm runs in O(n log n) or slides into O(n²):

Strategy	How it works	When to use
Last element	pivot = arr[high]. Simplest to implement.	Random or shuffled input
First element	pivot = arr[low]. Symmetric to last.	Same
Random element	Pick a random index in [low, high], swap with arr[high], then run normally.	When input may be sorted or reverse-sorted
Median-of-three	Take arr[low], arr[mid], arr[high]; use their median as pivot.	Production code

The problem with always choosing the last element: on an already-sorted array, every partition produces a left subarray of size n-1 and a right subarray of size 0. Recursion depth hits n levels and comparisons reach O(n²). Choosing a random pivot, or the median of three, makes that degenerate case statistically improbable on real input.

The std::sort in most C++ standard library implementations (see cppreference) uses introsort: it starts with quick sort, monitors recursion depth, and switches to heap sort if depth exceeds 2 * floor(log2(n)). This hybrid keeps worst-case complexity at O(n log n) without giving up quick sort’s average-case speed.

The Lomuto Partition: Step-by-Step Trace

The Lomuto scheme maintains two regions in the current subarray [low..high]: elements confirmed smaller than the pivot (indices low to i), and everything not yet examined. Variable j scans forward; i marks the right edge of the confirmed-smaller region.

Array: [10, 7, 8, 9, 1, 5], indices 0 to 5, pivot = arr[5] = 5.

• Set i = -1 (no confirmed-smaller elements yet).
• j=0: arr[0] = 10. Is 10 < 5? No. i stays -1.
• j=1: arr[1] = 7. Is 7 < 5? No. i stays -1.
• j=2: arr[2] = 8. Is 8 < 5? No. i stays -1.
• j=3: arr[3] = 9. Is 9 < 5? No. i stays -1.
• j=4: arr[4] = 1. Is 1 < 5? Yes. Increment i to 0. Swap arr[0] and arr[4]. Array becomes [1, 7, 8, 9, 10, 5].
• Scan ends. Place pivot: swap arr[i+1] = arr[1] with arr[high] = arr[5]. Array becomes [1, 5, 8, 9, 10, 7]. Return pi = 1.

Pivot 5 now sits at index 1, which is its correct position in the fully sorted array.

Remaining subarray to the right: [8, 9, 10, 7] (indices 2 to 5). Pivot = arr[5] = 7.

• i = 1, scan j=2..4: 8, 9, 10 are all larger than 7. No swaps.
• Place pivot: swap arr[2] = 8 with arr[5] = 7. Array: [1, 5, 7, 9, 10, 8]. Return pi = 2.

Right subarray: [9, 10, 8] (indices 3 to 5). Pivot = arr[5] = 8.

• i = 2, scan j=3..4: 9 and 10 are larger. No swaps.
• Place pivot: swap arr[3] = 9 with arr[5] = 8. Array: [1, 5, 7, 8, 10, 9]. Return pi = 3.

Right subarray: [10, 9] (indices 4 to 5). Pivot = arr[5] = 9.

• i = 3, scan j=4: 10 > 9. No swap.
• Place pivot: swap arr[4] = 10 with arr[5] = 9. Array: [1, 5, 7, 8, 9, 10]. Return pi = 4.

All remaining sub-calls have low >= high and return immediately. Final sorted result: [1, 5, 7, 8, 9, 10].

A common implementation error is returning i instead of i + 1 after placing the pivot. That shifts every subsequent partition boundary by one and produces incorrect sorted output.

Implementations in C, C++, Java, and Python

All four versions below use the Lomuto scheme with last-element pivot. The logic is identical across languages; only syntax changes.

C

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main(void) {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}
/* Output: 1 5 7 8 9 10 */

C++

#include <iostream>
#include <vector>

void swap(int &a, int &b) {
    int t = a; a = b; b = t;
}

int partition(std::vector<int> &arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int> &arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, static_cast<int>(arr.size()) - 1);
    for (int x : arr) std::cout << x << " ";
    return 0;
}
// Output: 1 5 7 8 9 10

Java

public class QuickSort {
    static void swap(int[] arr, int i, int j) {
        int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        for (int x : arr) System.out.print(x + " ");
    }
}
// Output: 1 5 7 8 9 10

Python

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr)  # [1, 5, 7, 8, 9, 10]

Python’s built-in sorted() and list.sort() use Timsort, not quick sort. The implementation above is for understanding the algorithm; production Python code should use the built-ins.

Time and Space Complexity

Code blocks are stripped when counting words, so the prose below makes the trade-offs explicit.

Case	Time	Space (stack)
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst	O(n²)	O(n)

In the best and average cases, each partition splits the subarray close to half, giving roughly log n levels of recursion. Space per level is constant: one stack frame. In the worst case, every partition produces a split of size 0 and size n-1, pushing recursion depth to n levels.

According to the Wikipedia Quicksort article, Hoare’s original 1962 partition scheme makes about three times fewer swaps than Lomuto on average, though both have the same O(n log n) average time complexity. For this reason, Hoare is preferred when swap cost is high, such as when elements are large structs.

Quick Sort vs Merge Sort

Criterion	Quick Sort	Merge Sort
Average time	O(n log n)	O(n log n)
Worst-case time	O(n²)	O(n log n)
Space	O(log n)	O(n)
Stable	No	Yes
Cache behaviour	Good (in-place)	Poor (auxiliary array)

Quick sort is the standard choice for in-memory sorting of primitive arrays because of its in-place access pattern and good cache locality. Merge sort wins when element order among equals must be preserved (stable sort), or when sorting linked lists, where the auxiliary-array cost disappears because the list can be split by relinking pointers rather than copying data.

Sorting algorithm questions appear regularly in the DSA rounds of campus placements. The 20 most-asked data structures interview questions covers heap sort, BST traversals, and linked-list operations that regularly appear alongside sorting in technical rounds.

For array fundamentals practice, finding the smallest and largest elements in an array reinforces the same single-scan loop reasoning that the Lomuto partition uses to place elements relative to the pivot.

The jump from O(n log n) to O(n²) on an already-sorted array comes from one upstream decision compounding at every recursion level. LLM pipeline design follows the same pattern: chunking strategy, retrieval depth, and prompt structure each compound across every query. TinkerLLM at ₹299 is a hands-on playground to experiment with those decisions on live prompts before they hit production.