Definition
- Quick sort – a divide-and-conquer, comparison-based sorting algorithm that sorts in place.
- Partition – rearranges elements so everything smaller than the pivot is on the left, everything larger on the right, and the pivot is in its final position.
- Recursion – after partition, recursively sort the left and right parts; no merge step needed.
- Pivot quality – determines performance: balanced partitions give O(n log n), worst pivots give O(n^2).
- Java usage –
Arrays.sortfor primitives uses a dual-pivot quicksort for its speed and cache friendliness.
Imagine the National Bank of India must sort a pile of transactions by amount. A clerk grabs one transaction as the pivot and splits the pile into smaller-than-pivot on the left and larger-than-pivot on the right, placing the pivot exactly between them where it now belongs forever. She then repeats the splitting on each sub-pile independently until every sub-pile has one item and the whole pile is sorted.
Understanding the Concepts
What is quick sort?
Quick sort is a divide-and-conquer sorting algorithm. It picks a pivot element, partitions the array so that everything smaller than the pivot sits to its left and everything larger to its right, places the pivot in its final sorted position, and then recursively sorts the two partitions. Unlike merge sort, there is no merge step because the partitioning already arranges elements relative to each other.
package com.bank.sort;
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // last element as pivot
int boundary = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
boundary++;
swap(arr, boundary, j);
}
}
swap(arr, boundary + 1, high);
return boundary + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
public static void main(String[] args) {
int[] amounts = {50000, 20000, 80000, 10000, 40000, 70000};
quickSort(amounts, 0, amounts.length - 1);
System.out.println("Sorted: " + Arrays.toString(amounts));
}
}
Sorted: [10000, 20000, 40000, 50000, 70000, 80000]
How does the Lomuto partition work?
The Lomuto partition scheme uses the last element as the pivot and a boundary index that marks the end of the "smaller" region. You scan the range, and whenever an element is less than or equal to the pivot, you swap it into the boundary and advance the boundary. Finally, you swap the pivot into the boundary slot.
package com.bank.sort;
public class PartitionTrace {
static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int b = lo - 1;
System.out.println("Pivot: " + pivot);
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
b++;
int t = arr[b]; arr[b] = arr[j]; arr[j] = t;
}
System.out.println(" j=" + j + " arr=" + java.util.Arrays.toString(arr) + " b=" + b);
}
int t = arr[b+1]; arr[b+1] = arr[hi]; arr[hi] = t;
System.out.println(" Pivot placed at " + (b+1) + ": " + java.util.Arrays.toString(arr));
return b + 1;
}
public static void main(String[] args) {
int[] arr = {50, 20, 80, 10, 40};
partition(arr, 0, arr.length - 1);
}
}
Pivot: 40
j=0 arr=[50, 20, 80, 10, 40] b=-1
j=1 arr=[20, 50, 80, 10, 40] b=0
j=2 arr=[20, 50, 80, 10, 40] b=0
j=3 arr=[20, 10, 80, 50, 40] b=1
Pivot placed at 2: [20, 10, 40, 50, 80]
Why does pivot quality matter?
With balanced partitions (pivot near the median), each recursion level processes n elements across log n levels, giving O(n log n). But if the pivot is always the smallest or largest element (e.g., choosing the last element on already-sorted input), one partition has n-1 elements and the other has 0, giving n levels and O(n^2) time.
package com.bank.sort;
public class PivotQuality {
public static void main(String[] args) {
System.out.println("Balanced partitions: O(n log n)");
System.out.println(" [1,2,...,50 | pivot=50 | 51,...,100]");
System.out.println();
System.out.println("Worst-case partitions: O(n^2)");
System.out.println(" [1] | pivot=1 | [2,3,4,...,100]");
System.out.println(" This happens with last-element pivot on sorted input.");
}
}
Balanced partitions: O(n log n)
[1,2,...,50 | pivot=50 | 51,...,100]
Worst-case partitions: O(n^2)
[1] | pivot=1 | [2,3,4,...,100]
This happens with last-element pivot on sorted input.
How do you choose a good pivot?
The two standard defences are median-of-three (pick the median of the first, middle, and last elements) and random pivot (swap a random element into the pivot position). Both make the worst case astronomically unlikely.
package com.bank.sort;
import java.util.Random;
public class RandomPivotSort {
static Random rand = new Random();
public static void quickSort(int[] arr, int lo, int hi) {
if (lo < hi) {
// Random pivot: swap random element to last position
int r = lo + rand.nextInt(hi - lo + 1);
int t = arr[r]; arr[r] = arr[hi]; arr[hi] = t;
int p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
}
static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi], b = lo - 1;
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) { b++; int tmp=arr[b]; arr[b]=arr[j]; arr[j]=tmp; }
}
int tmp = arr[b+1]; arr[b+1] = arr[hi]; arr[hi] = tmp;
return b + 1;
}
public static void main(String[] args) {
int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
quickSort(sorted, 0, sorted.length - 1);
System.out.println("Sorted: " + java.util.Arrays.toString(sorted));
}
}
Sorted: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Why is quick sort not stable?
Quick sort is not stable because the partition step swaps elements across long distances, which can reorder equal elements. For banking data where equal amounts must stay in chronological order, stability matters and merge sort or TimSort is preferred.
package com.bank.sort;
public class QuickSortUnstable {
public static void main(String[] args) {
System.out.println("Quick sort can reorder equal elements.");
System.out.println("Example: [5a, 3, 5b, 1] may become [1, 3, 5b, 5a].");
System.out.println("Use merge sort when stability is needed.");
}
}
Quick sort can reorder equal elements.
Example: [5a, 3, 5b, 1] may become [1, 3, 5b, 5a].
Use merge sort when stability is needed.
What is the time and space complexity?
| Case | Time | Space |
|---|---|---|
| Best | O(n log n) | O(log n) stack |
| Average | O(n log n) | O(log n) stack |
| Worst | O(n^2) | O(n) stack |
The space is for the recursion stack. In the best/average case the recursion depth is O(log n). In the worst case (maximally unbalanced) it is O(n), which can cause stack overflow.
How does Java use quick sort internally?
Java's Arrays.sort for primitive arrays uses a dual-pivot quicksort, which partitions the array into three parts using two pivots. This improves cache behaviour and reduces the number of swaps. For object arrays, Java uses TimSort (a stable merge sort variant) because stability matters for objects.
package com.bank.sort;
import java.util.Arrays;
public class JavaQuickSort {
public static void main(String[] args) {
int[] primitives = {80, 20, 60, 40, 100};
Arrays.sort(primitives); // dual-pivot quicksort
System.out.println("Primitives: " + Arrays.toString(primitives));
String[] objects = {"Rajesh", "Priya", "Pankaj"};
Arrays.sort(objects); // TimSort (stable)
System.out.println("Objects: " + Arrays.toString(objects));
}
}
Primitives: [20, 40, 60, 80, 100]
Objects: [Pankaj, Priya, Rajesh]
What are common mistakes?
The most common mistakes are: choosing the last element as pivot on nearly-sorted data (triggers worst case), forgetting to exclude the pivot from recursive calls (processes it twice), and using mid instead of mid + 1 or mid - 1 in the recursive bounds (incorrect partitions).
Visual Overview
Quick Sort Flow:
[50000, 20000, 80000, 10000, 40000, 70000]
pivot=70000
Partition:
[50000, 20000, 10000, 40000] | 70000 | [80000]
<--- smaller ---> final larger
Recurse left: Recurse right:
[50000, 20000, 10000, 40000] [80000] (done)
pivot=40000
[20000, 10000] | 40000 | [50000]
Continue until single elements...
Result: [10000, 20000, 40000, 50000, 70000, 80000]
Key Takeaway
Quick sort is a divide-and-conquer algorithm that picks a pivot, partitions the array so everything smaller is on the left and everything larger is on the right, and then recursively sorts the two partitions. The partition step does the real work: it places the pivot in its final sorted position in a single pass. There is no merge step because the partitioning already arranges elements relative to each other.
The performance depends entirely on pivot quality. Balanced partitions give O(n log n), but consistently bad pivots (smallest or largest) degrade to O(n^2). Median-of-three or random pivot selection makes the worst case astronomically unlikely in practice.
Quick sort is in-place with O(log n) stack space and is cache-friendly with small constant factors, which is why it is often the fastest sort in practice. Java uses a dual-pivot quicksort for primitive arrays in Arrays.sort. However, it is not stable, so Java uses TimSort for object arrays where preserving the order of equal elements matters.
In a banking system at the National Bank of India, quick sort is used for large in-memory arrays of transaction amounts when stability is not required and memory is tight. The pivot is chosen by median-of-three to avoid the worst case on nearly-sorted feeds.
Remember one sentence: quick sort partitions around a pivot in-place and recurses on both sides, averaging O(n log n) but needing a good pivot to avoid the rare quadratic worst case.
---