Quick Sort Fixes One Pivot at a Time

Partitioning fixes the pivot, not the whole array

Quick Sort starts by choosing a pivot and partitioning its range around that value. With Lomuto partitioning, the last value in the range is the pivot. The boundary pointer i marks the end of the values that are at most the pivot, while the scan pointer j visits each other value from left to right. When arr[j] is at most the pivot, the boundary moves right and the two values are swapped. Values greater than the pivot stay on the right side of the boundary.

Start: [7, 2, 1, 6, 8, 5, 3, 4]
Pivot: 4 at index 7
Boundary i: -1

j = 0, compare 7 with 4: 7 is greater, no swap, i = -1
j = 1, compare 2 with 4: 2 is at most 4, move i to 0, swap indices 0 and 1
      [2, 7, 1, 6, 8, 5, 3, 4]
j = 2, compare 1 with 4: 1 is at most 4, move i to 1, swap indices 1 and 2
      [2, 1, 7, 6, 8, 5, 3, 4]
j = 3, compare 6 with 4: 6 is greater, no swap, i = 1
j = 4, compare 8 with 4: 8 is greater, no swap, i = 1
j = 5, compare 5 with 4: 5 is greater, no swap, i = 1
j = 6, compare 3 with 4: 3 is at most 4, move i to 2, swap indices 2 and 6
      [2, 1, 3, 6, 8, 5, 7, 4]

After the scan, swap the pivot with the value at i + 1, index 3:
      [2, 1, 3, 4, 8, 5, 7, 6]

The final swap places 4 immediately after the values at most 4. Its final index is 3, so no later recursive call needs to include index 3. The result does not promise that [2, 1, 3] is sorted, and it does not promise that [8, 5, 7, 6] is sorted. It promises only that every value in indices 0-2 is at most 4, every value in indices 4-7 is greater than 4, and 4 itself is in its final position.

Recursive calls sort the two ranges that partitioning leaves unfinished

After the first partition, Quick Sort calls itself on range 0-2 and range 4-7. The pivot at index 3 is excluded because its position is already final. Each later partition has the same effect: it fixes one more pivot and leaves smaller ranges around it.

Current array: [2, 1, 3, 4, 8, 5, 7, 6]

Range 0-2, pivot 3:
  2 and 1 are at most 3, so the pivot finishes at index 2.
  Array remains [2, 1, 3, 4, 8, 5, 7, 6].
  New ranges: 0-1 and 3-2.

Range 0-1, pivot 1:
  2 is greater than 1, so swap the pivot with 2.
  Array becomes [1, 2, 3, 4, 8, 5, 7, 6].
  New ranges: 0--1 and 1-1.

Range 4-7, pivot 6:
  8 is greater than 6, so do not swap.
  5 is at most 6, so swap 5 with 8.
  Array becomes [1, 2, 3, 4, 5, 8, 7, 6].
  7 is greater than 6, so do not swap.
  Swap the pivot 6 with 8 at index 5.
  Array becomes [1, 2, 3, 4, 5, 6, 7, 8].
  New ranges: 4-4 and 6-7.

Range 6-7, pivot 8:
  7 is at most 8, so the pivot stays at index 7.
  New ranges: 6-6 and 8-7.

The ranges 3-2, 0--1, 1-1, 4-4, 6-6, and 8-7 all have size 0 or 1. They stop without partitioning because an empty range has nothing to arrange and a one-element range is already sorted. Once every branch stops, the array is [1, 2, 3, 4, 5, 6, 7, 8].

Pivot balance determines how much work Quick Sort performs

A partition scans its range once, so the work at one recursion level is linear in the number of values still being handled. In the running example, the first level scans seven values. The next level handles ranges of sizes 3 and 4, so it scans five values in total. Later levels handle smaller disjoint ranges. The total work across one level is still O(n), even though the work is split between several recursive calls.

The number of levels depends on how balanced the splits are. The first pivot, 4, creates ranges of sizes 3 and 4, which are reasonably balanced. The later pivots also divide the remaining values into short branches. With splits that stay reasonably balanced, there are about log n levels, each costing O(n) in total, giving expected time O(n log n).

A pivot can instead finish at one end of its range. Then one recursive range has size zero and the other has size only one smaller than before. The next partition scans almost the same number of values again, and this repeats for about n levels. The work becomes n + (n - 1) + (n - 2) and so on, which is O(n^2), with recursion depth O(n) instead of O(log n).

The first partition produces [2, 1, 3, 4, 8, 5, 7, 6].

In-place partitioning saves an auxiliary array but does not preserve equal-element order

The swaps in the running example rearrange the values inside the original array. Lomuto partitioning does not create a second array holding the values from the left and right sides, so its partition storage is O(1). That is why this form of Quick Sort is called in-place.

In-place does not mean that the algorithm uses no extra memory. Every recursive call stores its range boundaries and other call information on the recursion stack. With reasonably balanced splits, the recursion depth and expected recursion-stack space are O(log n). If pivots repeatedly finish at an endpoint, the depth and stack space can grow to O(n).

This implementation is also not stable. Stability would preserve the original relative order of elements with equal keys. A swap between the boundary and the scan position can move an equal-key element past another equal-key element, so the partition's rearrangement does not promise that order. In-place describes where partitioning stores values, not whether equal values keep their order or whether the recursion stack disappears.