Pattern visualizer
Quick Sort
Instead of merging sorted halves, quicksort picks a pivot and rearranges the array so everything <= pivot ends up before it and everything > pivot ends up after — then the pivot is already in its final sorted position. Lomuto's scheme does this with one pass: walk a scanning pointer j across the array, and whenever arr[j] <= pivot, swap it into a growing 'small' region tracked by pointer i. Recurse on the two pieces on either side of the placed pivot. Animated on: arr = [10,7,8,9,1,5] — sort the array using Lomuto partitioning..
Lomuto partition around a pivot
time O(n log n) averagespace O(log n)step 1 / 11
10
[0]7
[1]8
[2]9
[3]1
[4]5
[5]line 3
Lomuto partition picks the last element as pivot: 5. Scan the rest, moving anything <= pivot to the front.
Pseudocode
1FUNCTION quickSort(arr, lo, hi):2 IF lo >= hi: RETURN (nothing to sort)3 pivot = arr[hi] (the last element)4 i = lo - 1 (end of the 'small' region)5 FOR j from lo to hi-1:6 IF arr[j] <= pivot:7 move i one step right; swap arr[i] and arr[j]8 swap arr[i+1] and arr[hi] (drop the pivot into place)9 quickSort(arr, lo, i); quickSort(arr, i+2, hi) (sort both sides)
← / → step · space play · Home restart