How Quicksort can be done “in place”

Quicksort can be done “in place”, just by swapping items within the same list, without creating another list-space into which items from the previous list are moved.

It is done on computers “in place”. Here is one way it can be done “in place”.

Set two markers, marker 1 on the first place in the list, one on the last place. (The markers are on the places, not the items in the places).

Everything to the left of marker 1 (so far, nothing) has to go before the pivot, everything to the right of marker 2 (so far, nothing) has to be go after.

Scan forward from marker 1 (starting with, and including, the item in the marker 1 position) until you find an item which should go after the pivot. Then scan backwards from marker 2 (starting with, and including, the item in the marker 2 position) until you find an element which should go before the pivot.

Swap those two elements. Move marker 1 to the place after the one out of which you’ve just swapped an “above” item, and into which you’ve just swapped a “below” item. Move marker 2 to the place before the one out of which you’ve just swapped a “below” item, and into which you’ve just swapped an “above” item.

Keep on until the two markers meet, then swap the pivot to be between the “below” and “above” items.

Here’s an example.

9 1 8 2 7 3 6 4 5

in ascending order

Select pivot and markers – 7

*9 1 8 2 [7] 3 6 4 5*

5 *1 8 2 [7] 3 6 4* 9

5 1 4 *2 [7] 3 6* 8 9

5 1 4 2 [7] 3 *6* 8 9

5 1 4 2 3 6 [7] 8 9

The first pass is complete.