Sorting

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.go 
package main

import "fmt"

func partition(arr []int, low int, high int) int {
	pivot := arr[high]
	i := low - 1
	for j := low; j < high; j++ {
		if arr[j] <= pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[high] = arr[high], arr[i+1]
	return i + 1
}

func quickSort(arr []int, low int, high int) {
	if low < high {
		pivotIndex := partition(arr, low, high)
		quickSort(arr, low, pivotIndex-1)
		quickSort(arr, pivotIndex+1, high)
	}
}

func main() {
	arr := []int{4, 1, 5, 2, 3}
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

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.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

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

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

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].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

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

Implementation notes

  • Go builds arr with the slice literal []int{4, 1, 5, 2, 3}; quickSort receives that slice header and mutates the shared backing array in place.
  • quickSort(arr, low, high) recurses only when low < high; main starts with bounds 0 and len(arr)-1.
  • Lomuto partition chooses pivot := arr[high], initializes i := low - 1, and scans j := low; j < high; j++.
  • Comparisons use arr[j] <= pivot; when true, i++ runs before the tuple swap arr[i], arr[j] = arr[j], arr[i]. The pivot is placed with arr[i+1], arr[high] = arr[high], arr[i+1].
  • The trace records the first partition: keep 4, swap 1 left, keep 5, swap 2 left, then swap pivot 3 into index 2, producing [1, 2, 3, 4, 5].
  • Recursive calls on left [1, 2] and right [4, 5] are summarized in the trace; there is no separate bad-pivot or degradation trace frame here.
  • fmt.Println(arr) prints Go's default slice format [1 2 3 4 5]. Indexed accesses rely on the checked low/high bounds and Go's normal bounds checks.
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.