Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail

partition() {
	local low=$1
	local high=$2
	local pivot=${arr[high]}
	local i=$((low - 1))
	local j
	local tmp
	for ((j = low; j < high; j++)); do
		if ((arr[j] <= pivot)); then
			i=$((i + 1))
			tmp=${arr[i]}
			arr[i]=${arr[j]}
			arr[j]=$tmp
		fi
	done
	tmp=${arr[i+1]}
	arr[i+1]=${arr[high]}
	arr[high]=$tmp
	pivot_index=$((i + 1))
}

quick_sort() {
	local low=$1
	local high=$2
	if ((low < high)); then
		partition "$low" "$high"
		local p=$pivot_index
		quick_sort "$low" "$((p - 1))"
		quick_sort "$((p + 1))" "$high"
	fi
}

arr=(4 1 5 2 3)
pivot_index=0
quick_sort 0 $((${#arr[@]} - 1))
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Complexity

Time: O(n^2) worst, O(n log n) average
Space: O(log n) average call stack
Stable: no

Implementation notes

arr=(4 1 5 2 3) is the pinned Bash indexed array, and quick_sort mutates it in place by index.
quick_sort "$low" "$high" receives integer bounds. if ((low < high)) is Bash arithmetic evaluation for the recursive base case.
partition "$low" "$high" chooses the last element as the pivot with pivot=${arr[high]}.
i=$((low - 1)) marks the end of the smaller-or-equal region. The scan variable j walks from low to high - 1.
if ((arr[j] <= pivot)); then is a numeric comparison. When it passes, i moves right and the tmp lines swap arr[i] with arr[j].
After the scan, another tmp swap moves the pivot into arr[i+1], and pivot_index=$((i + 1)) tells quick_sort where to split.
The recursive calls sort low..p-1 and p+1..high. Lomuto quicksort is not stable because swaps can move equal values around.

First partition replay

pivot 3 in [4, 1, 5, 2, 3]
4 > 3: keep right side
1 <= 3: swap into left side -> [1, 4, 5, 2, 3]
5 > 3: keep right side
2 <= 3: swap into left side -> [1, 2, 5, 4, 3]
pivot swap: [1, 2, 3, 4, 5]

Final output uses the shared Bash formatter: printf '[', for v in "${arr[@]}", printf '%s%d' "$sep" "$v", and printf ']\n'.

pivot The final element is moved to the boundary between smaller and larger values.

partition One scan rearranges the current range before the recursive calls.