Quick Sort
Quick sort is a highly efficient, in-place divide-and-conquer sorting algorithm that selects a "pivot" element and partitions the array into two sub-arrays — elements less than the pivot and elements greater than the pivot — then recursively sorts each sub-array. It achieves an average time complexity of O(n log n) and is often faster in practice than merge sort due to better cache performance and lower constant factors. Quick sort is widely used in standard library implementations, including the C++ STL and Java's Arrays.sort for primitive types.
Key Formula
T(n) = T(k) + T(n - k - 1) + O(n)
LaTeX: T(n) = T(k) + T(n - k - 1) + O(n)
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Time to sort n elements | operations |
| k | Number of elements in the left partition | elements |
| n - k - 1 | Number of elements in the right partition | elements |
| O(n) | Time to partition the array | operations |
Worked Example
Problem
Sort [10, 80, 30, 90, 40, 50, 70] using quick sort with the last element as pivot.
Solution
Step 1: Pivot = 70. Partition: elements < 70 go left, > 70 go right → [10, 30, 40, 50, 70, 80, 90], pivot at index 4. Step 2: Recursively sort left sub-array [10, 30, 40, 50]: pivot = 50, partition → [10, 30, 40, 50]. Step 3: Recursively sort [10, 30, 40]: pivot = 40 → [10, 30, 40]. Step 4: Right sub-array [80, 90]: pivot = 90 → [80, 90]. Step 5: Combine all.
Answer
Sorted array: [10, 30, 40, 50, 70, 80, 90].
Quick Sort Complexity and Properties
| Property | Value | Notes |
|---|---|---|
| Best Case Time | O(n log n) | Pivot always splits evenly |
| Average Case Time | O(n log n) | Random pivot selection |
| Worst Case Time | O(n²) | Already sorted, bad pivot |
| Space Complexity | O(log n) | Call stack depth |
| Stability | Unstable | Relative order not preserved |
| In-place | Yes | No auxiliary array needed |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements in place. It works in two phases: first building a max-heap from the input array, then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted portion. Heap sort guarantees O(n log n) time complexity in all cases and O(1) auxiliary space, making it optimal for scenarios where both time efficiency and memory constraints matter.
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Quick sort was developed by British computer scientist Tony Hoare in 1959 while working as an exchange student at Moscow State University, and published in 1961. Hoare chose the name to reflect the algorithm's empirically fast performance relative to other sorting methods of the time.