Lomuto Partition Quicksort

Lomuto partition quicksort uses a simple partition scheme based on a single boundary index. It scans the array once, moving elements smaller than the pivot to the left.

It is easier to implement and reason about than Hoare partition, though it performs more swaps and comparisons in practice.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Idea

Choose the last element as the pivot. Maintain an index $i$ that marks the boundary between elements less than or equal to the pivot and the rest.

As you scan from left to right:

if the current element is less than or equal to the pivot, swap it into the left region
otherwise leave it in place

At the end, place the pivot at index $i$ .

Algorithm

lomuto_quicksort(A, lo, hi):
    if lo >= hi:
        return

    p = lomuto_partition(A, lo, hi)

    lomuto_quicksort(A, lo, p - 1)
    lomuto_quicksort(A, p + 1, hi)

lomuto_partition(A, lo, hi):
    pivot = A[hi]
    i = lo

    for j from lo to hi - 1:
        if A[j] <= pivot:
            swap A[i] and A[j]
            i += 1

    swap A[i] and A[hi]
    return i

Example

Let:

A = [4, 2, 7, 1, 5]

Pivot:

5

Scan:

step	j	value	action	array
1	0	4	swap with i	[4, 2, 7, 1, 5]
2	1	2	swap	[4, 2, 7, 1, 5]
3	2	7	skip	[4, 2, 7, 1, 5]
4	3	1	swap	[4, 2, 1, 7, 5]

Final swap with pivot:

[4, 2, 1, 5, 7]

Pivot index:

3

Correctness

The loop maintains the invariant that all elements before index $i$ are less than or equal to the pivot. After scanning all elements, swapping the pivot into position $i$ ensures that all elements before it are smaller and all elements after it are larger. Recursively sorting both sides produces a sorted array.

Complexity

case	time
best	$O(n \log n)$
average	$O(n \log n)$
worst	$O(n^2)$

Worst case occurs when the pivot consistently produces unbalanced partitions, such as already sorted input.

Space:

case	space
average recursion	$O(\log n)$
worst recursion	$O(n)$

Properties

property	value
stable	no
in-place	yes
simplicity	high
swaps	more than Hoare
robustness	lower

Notes

Lomuto partition is widely used for teaching because of its clarity. In production systems, Hoare partition or more advanced schemes are often preferred due to better performance.

This variant serves as a clean baseline for understanding quicksort.

Implementation

def lomuto_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        p = partition(lo, hi)
        sort(lo, p - 1)
        sort(p + 1, hi)

    def partition(lo, hi):
        pivot = a[hi]
        i = lo

        for j in range(lo, hi):
            if a[j] <= pivot:
                a[i], a[j] = a[j], a[i]
                i += 1

        a[i], a[hi] = a[hi], a[i]
        return i

    sort(0, len(a) - 1)
    return a

func LomutoQuickSort(a []int) {
	var sort func(int, int)

	sort = func(lo, hi int) {
		if lo >= hi {
			return
		}

		p := lomutoPartition(a, lo, hi)
		sort(lo, p-1)
		sort(p+1, hi)
	}

	sort(0, len(a)-1)
}

func lomutoPartition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo

	for j := lo; j < hi; j++ {
		if a[j] <= pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}

	a[i], a[hi] = a[hi], a[i]
	return i
}