# Lomuto Partition Quicksort

# 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

```text id="n4k2xp"
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)
```

```text id="c8s3qt"
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

```python id="k2m8xp"
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
```

```go id="v7n3qd"
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
}
```