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

int partition(List<int> arr, int low, int high) {
  final pivot = arr[high];
  var i = low - 1;
  for (var j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      final tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
  }
  final tmp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = tmp;
  return i + 1;
}

void quickSort(List<int> arr, int low, int high) {
  if (low < high) {
    final pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}

void main() {
  final arr = <int>[4, 1, 5, 2, 3];
  quickSort(arr, 0, arr.length - 1);
  print(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.

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

Keep the explicit algorithmic steps instead of calling a standard-library sort. This checked-in replay shows each comparison and swap in the first partition, then summarizes the recursive calls on already-sorted sides.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

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.