Quick Sort - Algorithms - Computer Science Engineering (CSE)

Introduction

Quick Sort is a divide and conquer sorting algorithm. It picks an element called the pivot and partitions the array around the pivot so that elements smaller than the pivot appear before it and elements greater than the pivot appear after it. The algorithm then recursively sorts the partitions.

Common strategies to choose the pivot include:

1. Always pick the first element as pivot.
2. Always pick the last element as pivot.
3. Pick a random element as pivot.
4. Pick the median (or median-of-three) as pivot.

The central routine is partition(), which places the pivot at its correct sorted position and rearranges elements around it in linear time.

Pseudo code for QuickSort

/* low --> Starting index, high --> Ending index */ quickSort(arr[], low, high) { if (low < high)="" {="" pi="" is="" partitioning="" index,="" arr[pi]="" is="" now="" at="" right="" place="" */="" pi="partition(arr," low,="" high);="" quicksort(arr,="" low,="" pi="" -="" 1);="" before="" pi="" quicksort(arr,="" pi="" +="" 1,="" high);="" after="" pi="" }="">

Partition Algorithm

There are several partition schemes. The following adopts the scheme used in CLRS (Lomuto partition scheme) where the last element is taken as pivot. The method scans the array from left to right, maintaining an index i that marks the boundary of elements known to be less than or equal to the pivot. For each element scanned, if it is ≤ pivot, i is incremented and that element is swapped into the "less-than-or-equal" region.

Pseudo code for partition()

/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ partition(arr[], low, high) { // pivot (Element to be placed at right position) pivot = arr[high]; i = (low - 1); // Index of smaller element for (j = low; j <= high="" -="" 1;="" j++)="" {="" if="" current="" element="" is="" smaller="" than="" or="" equal="" to="" pivot="" if="" (arr[j]=""><= pivot)="" {="" i++;="" increment="" index="" of="" smaller="" element="" swap="" arr[i]="" and="" arr[j];="" }="" }="" swap="" arr[i="" +="" 1]="" and="" arr[high];="" return="" (i="" +="" 1);="">

Illustration of partition()

Consider the array:

arr[] = {10, 80, 30, 90, 40, 50, 70}

Indexes: 0 1 2 3 4 5 6

low = 0, high = 6, pivot = arr[high] = 70

Initialize index of smaller element: i = -1

Traverse j from low to high - 1:

• j = 0: arr[0] = 10 ≤ 70 → i = 0, swap arr[0] and arr[0]. Array: {10, 80, 30, 90, 40, 50, 70}.
• j = 1: arr[1] = 80 > 70 → do nothing.
• j = 2: arr[2] = 30 ≤ 70 → i = 1, swap arr[1] and arr[2]. Array: {10, 30, 80, 90, 40, 50, 70}.
• j = 3: arr[3] = 90 > 70 → do nothing.
• j = 4: arr[4] = 40 ≤ 70 → i = 2, swap arr[2] and arr[4]. Array: {10, 30, 40, 90, 80, 50, 70}.
• j = 5: arr[5] = 50 ≤ 70 → i = 3, swap arr[3] and arr[5]. Array: {10, 30, 40, 50, 80, 90, 70}.

After the loop, place pivot at correct position by swapping arr[i+1] and arr[high]:

swap arr[4] and arr[6] → Array: {10, 30, 40, 50, 70, 90, 80}.

Now pivot 70 is at index 4; elements left of it are ≤ 70 and elements right of it are ≥ 70.

Implementations

The standard implementations for QuickSort are available in many languages. The following placeholders point to typical code examples for each language.

C++14

Java

Python3

Example Output

Sorted array:

1 5 7 8 9 10

Analysis of QuickSort

The running time T(n) for QuickSort on n elements (when partition separates k elements to left of pivot) satisfies:

T(n) = T(k) + T(n - k - 1) + Θ(n)

The Θ(n) term is for the partition step. The running time depends on how balanced the partitions are; this is determined by the pivot selection strategy and the input distribution.

Cases

1. Worst Case:

   The worst case occurs when the pivot always ends up being the greatest or smallest element, producing highly unbalanced partitions. For the Lomuto partition with last element as pivot, the worst case happens when the array is already sorted (either increasing or decreasing).

   Recurrence:

   T(n) = T(n - 1) + Θ(n)

   Solution: Θ(n²).

2. Best Case:

   The best case occurs when the partition always splits the array into two equal halves (or close to equal), for example when the pivot is the median.

   Recurrence:

   T(n) = 2T(n/2) + Θ(n)

   Solution: Θ(n log n) (by the Master Theorem).

3. Average Case:

   Average-case analysis averages over all possible pivot positions or permutations of input. If partitions are reasonably balanced on average, QuickSort achieves Θ(n log n) expected running time. For example, with partitions of sizes approximately n/9 and 9n/10 the recurrence

   T(n) = T(n/9) + T(9n/10) + Θ(n)

   also solves to O(n log n).

   Although worst-case complexity is O(n²), QuickSort tends to be faster in practice than other O(n log n) sorts for arrays because of low constant factors and excellent locality of reference. Randomised QuickSort avoids input patterns that cause worst-case behaviour by choosing a random pivot.

Stability

The typical in-place QuickSort is not stable because swapping can change the relative order of equal elements. Stability can be achieved with extra bookkeeping (for example incorporating original indices into comparisons), but that costs extra space or complexity.

In-place

QuickSort qualifies as an in-place sorting algorithm in the broad sense because it requires only O(log n) extra space on average for recursion stack (or O(n) in the worst-case recursion) and does not require an auxiliary array for partitioning.

3-Way QuickSort

When there are many duplicate keys, standard two-way partitioning performs poorly because equal elements are processed repeatedly. 3-way QuickSort (Dutch National Flag partitioning) divides the array into three parts:

• arr[l..i] - elements less than pivot,
• arr[i+1..j-1] - elements equal to pivot,
• arr[j..r] - elements greater than pivot.

This reduces comparisons and swaps when duplicates are common and can improve performance significantly for such inputs.

How QuickSort is implemented for Linked Lists

QuickSort can be adapted to linked lists, but some considerations differ because linked lists do not support constant-time random access.

QuickSort on Singly Linked List

The idea is to partition nodes around a chosen pivot by changing links rather than swapping data. The partition function returns the pivot node after placing it at its correct position. The recursive routine then sorts the sublists before and after the pivot. The algorithm changes pointers, not node data, and achieves the same asymptotic time complexity as for arrays.

Implementation notes:

• Use the last node in the current list as pivot for ease of implementation.
• Traverse the list; move nodes greater than the pivot to the tail and leave smaller nodes in place.
• After partitioning, recursively sort the left and right sublists defined by the pivot node.

Implementations (Singly Linked List)

Example Output (Linked List)

Linked List before sorting

30 3 4 20 5

Linked List after sorting

3 4 5 20 30

Iterative Quick Sort

Recursive QuickSort uses function-call stack space to store the low and high indices. An iterative implementation simulates the recursion using an explicit stack of index pairs. The partition process is identical to recursive QuickSort, so the same pivot-selection strategies apply.

Typical recursive implementation (for reference)

Java (recursive example)

Output:

2 2 4 6 9

Optimisations commonly applied

1. Choose a better pivot to avoid worst-case behaviour on already sorted input: use a random pivot, the middle element, or median of first/middle/last (median-of-three).
2. Recur first on the smaller partition and use tail recursion (or an explicit loop) for the larger, to reduce maximum recursion depth.
3. Switch to insertion sort for small subarrays (below a threshold like 7), because insertion sort is faster on small inputs due to low overhead.

These optimisations are applicable to the iterative version as well. The explicit stack should first push the indices of the smaller half to limit stack size. Use insertion sort for small ranges.

Iterative implementations

Python

Other languages

Output:

1 2 2 3 3 3 4 5

QuickSort on Doubly Linked List

QuickSort for doubly linked lists follows a similar idea to arrays: find the last node, use it as pivot, partition by rearranging pointers, and recursively sort the sublists before and after the pivot. A C++ implementation commonly uses pointers to the first and last nodes in each recursive call. The partition function returns a pointer to the pivot node.

Implementations (Doubly Linked List)

Output (Doubly Linked List)

Linked List before sorting

30 3 4 20 5

Linked List after sorting

3 4 5 20 30

Time Complexity: The time complexity for QuickSort on linked lists remains the same in asymptotic terms: O(n²) worst-case and O(n log n) average/best case. The worst-case arises for already-sorted lists with certain pivot choices.

Randomised QuickSort on linked lists: Random pivot selection on linked lists is less efficient because selecting a random element requires traversal; therefore randomised QuickSort is not as straightforward or efficient for linked lists as it is for arrays.

Why QuickSort is preferred for arrays; when MergeSort is preferable

QuickSort advantages for arrays:

• In-place in general: QuickSort needs only O(log n) extra space on average for recursion (no large auxiliary arrays), whereas MergeSort commonly needs O(n) extra space to merge arrays.
• Better cache performance: QuickSort has good locality of reference when operating on arrays, which yields better practical performance.
• Low constant factors: QuickSort's inner loop is typically simpler and faster in practice than MergeSort's merge operations.

When MergeSort is preferable:

• For linked lists: MergeSort performs well because merging two sorted linked lists can be done in O(1) extra space and linear time using pointer manipulations.
• When stable sorting is required: MergeSort is stable by nature (unless implemented otherwise), while QuickSort is not by default.
• When worst-case guarantees are important: MergeSort guarantees O(n log n) worst-case time, while QuickSort has O(n²) worst case unless randomisation or careful pivot selection is used.

Optimising QuickSort stack usage to O(log n) worst-case

Typical strategies to bound extra space to O(log n) in the worst case include:

• Always recurse on the smaller partition and iterate on the larger partition (convert to tail recursion). This ensures maximum depth is O(log n).
• Use an explicit stack and push only the smaller partition first; process the larger partition within the loop.
• Combine with pivot-selection strategies (randomised pivot or median-of-three) to avoid pathological inputs.

• Quiz on QuickSort
• Recent Articles on QuickSort
• Coding practice for sorting.

Iterative QuickSort - code examples and outputs

Iterative variants exist for many languages; the partition function remains the same as recursive variants. The following placeholders point to typical iterative implementations and language-specific examples.

Output:

2 2 4 6 9

Output:

1 2 2 3 3 3 4 5

Practical tips for interviews and competitive programming

• Understand partition schemes: Lomuto (single index) and Hoare (two-index) partitions and their trade-offs.
• Know pivot strategies and when to use randomisation or median-of-three to avoid worst-case inputs.
• Be prepared to explain time and space complexity in best, average and worst cases and to derive the recurrence relations.
• Know when to switch to insertion sort for small subarrays and how this improves actual runtime.
• Be able to convert a recursive algorithm to an iterative one using an explicit stack for practice and interview discussion.
• For linked lists, explain why MergeSort is often better and why random pivot selection is less practical.

References and further reading

• CLRS - for partition schemes and theoretical analysis (the Lomuto scheme is described in many algorithm textbooks).
• Standard library implementations of qsort/quick sort in various languages for practical optimisations (median-of-three, insertion sort threshold, tail recursion elimination).