Quick Sort explained step-by-step: Lomuto partitioning scheme, pivot selection strategies, in-place recursion tree, cache locality, and JavaScript implementation.
Quick Sort is one of the most efficient and widely used sorting algorithms. Invented by Tony Hoare in 1959, it employs the divide-and-conquer strategy by selecting a "pivot" element and partitioning the array so that all values smaller than the pivot precede it, and all values greater follow it.
Unlike Merge Sort, Quick Sort sorts elements in-place with minimal auxiliary memory (only O(log n) call stack space on average) and exhibits outstanding CPU cache locality. Because of its raw practical speed, Quick Sort (paired with median-of-three pivot selection and fallback to Heap Sort / Insertion Sort in Introsort) is the core algorithm inside modern language runtimes and standard libraries.
Choose a pivot element from the subarray (e.g., the last element in Lomuto partition, or a randomized / median-of-three choice).
Iterate through the array with pointer j. Whenever arr[j] < pivot, increment pointer i and swap arr[i] with arr[j].
Swap arr[i + 1] with arr[high]. The pivot is now at its exact sorted index (pi = i + 1), with smaller items on the left and larger on the right.
Recursively call Quick Sort on the left partition (low to pi - 1) and right partition (pi + 1 to high). Base case is low >= high.
1function quickSort(arr, low = 0, high = arr.length - 1) {2 if (low < high) {3 // pi is partitioning index, arr[pi] is now at right place4 const pi = partition(arr, low, high);5 6 // Recursively sort elements before and after partition7 quickSort(arr, low, pi - 1);8 quickSort(arr, pi + 1, high);9 }10 return arr;11}12 13function partition(arr, low, high) {14 const pivot = arr[high]; // Lomuto pivot (last element)15 let i = low - 1; // Index of smaller element16 17 for (let j = low; j < high; j++) {18 // If current element is smaller than the pivot19 if (arr[j] < pivot) {20 i++;21 [arr[i], arr[j]] = [arr[j], arr[i]];22 }23 }24 25 // Place pivot in its correct sorted position26 [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];27 return i + 1;28}29 30// Example usage:31// quickSort([10, 80, 30, 90, 40, 50, 70]); // [10, 30, 40, 50, 70, 80, 90]Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Ready — press Play or use step controls to walk through the algorithm.
Comparisons
0
Swaps / Shifts
0
Passes / Depth
0
Elements
10
Test your understanding of Quick Sort complexity and step mechanics.
Q1.What triggers the worst-case O(n²) time complexity in standard Quick Sort with last-element pivot?
Q2.What is the auxiliary space complexity of Quick Sort on average?
Apply Quick Sort to real coding interview questions.
Given an array of integers nums, sort the array in ascending order.