DSA Tracker

Visualize

Quick Sort

Lomuto partition around a pivot

time O(n log n) averagespace O(log n)

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.

Details

Animated on: arr = [10,7,8,9,1,5] — sort the array using Lomuto partitioning.

Problem:Quick SortMedium

Lomuto partition around a pivot

step 1 / 11

10
[0]
7
[1]
8
[2]
9
[3]
1
[4]
5
[5]

Lomuto partition picks the last element as pivot: 5. Scan the rest, moving anything <= pivot to the front.

  • pivot=5· arr[5] = 5
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

Every step in words

Show all 11 steps
  1. Lomuto partition picks the last element as pivot: 5. Scan the rest, moving anything <= pivot to the front.
  2. j=0: 10 > 5, leave it — it belongs in the 'greater than pivot' region.
  3. j=1: 7 > 5, skip.
  4. j=2: 8 > 5, skip.
  5. j=3: 9 > 5, skip.
  6. j=4: 1 <= 5. Swap arr[0] and arr[4] to grow the 'less-than-or-equal-to-pivot' region.
  7. After the swap: [1,7,8,9,10,5]. i=0 marks the boundary of the <=pivot region.
  8. Scan finished. Swap the pivot (idx5) into position i+1=1, right after the <=pivot region.
  9. Pivot 5 is now at index 1 — its final sorted position. Left side [1] is all <=5, right side [8,9,10,7] is all >5.
  10. Recurse: left partition [1] is trivially sorted. Recursively quicksort the right partition [8,9,10,7] (indices 2-5).
  11. After the right partition finishes sorting, the fully sorted array is [1,5,7,8,9,10].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Quick Sort in the editorAll Sorting problemsBack to roadmap