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.pl 
use strict; use warnings;
sub partition {
	my ($arr, $low, $high) = @_;
	my $pivot = $arr->[$high];
	my $i = $low - 1;
	for (my $j = $low; $j < $high; $j++) {
		if ($arr->[$j] <= $pivot) {
			$i++;
			@$arr[$i, $j] = @$arr[$j, $i];
		}
	}
	@$arr[$i + 1, $high] = @$arr[$high, $i + 1];
	return $i + 1;
}

sub quick_sort {
	my ($arr, $low, $high) = @_;
	if ($low < $high) {
		my $pivot_index = partition($arr, $low, $high);
		quick_sort($arr, $low, $pivot_index - 1);
		quick_sort($arr, $pivot_index + 1, $high);
	}
}

my @arr = (4, 1, 5, 2, 3);
quick_sort(\@arr, 0, $#arr);
print "[" . join(", ", @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

  • my @arr = (4, 1, 5, 2, 3) declares the pinned Perl array with the @ sigil.
  • quick_sort(\@arr, 0, $#arr) passes an array reference plus zero-based bounds; $#arr is the last valid index.
  • partition unpacks its parameters with my ($arr, $low, $high) = @_, so $arr is a scalar reference to the array.
  • Array elements are read through the reference, such as $arr->[$high] and $arr->[$j].
  • Lomuto pivot selection is my $pivot = $arr->[$high], so the first pivot is the final value 3.
  • my $i = $low - 1 starts the smaller-value boundary at -1 for the first partition.
  • The partition scan is for (my $j = $low; $j < $high; $j++), so it compares indexes 0 through 3 and leaves the pivot at index 4 until the final placement.
  • The comparison is numeric and inclusive: if ($arr->[$j] <= $pivot).
  • Swaps use Perl slice/list assignment on the referenced array: @$arr[$i, $j] = @$arr[$j, $i].
  • In the trace, 4 <= 3 is false, so 4 stays on the right side and i remains -1.
  • 1 <= 3 is true, so i becomes 0 and the array changes to [1, 4, 5, 2, 3].
  • 5 <= 3 is false, leaving [1, 4, 5, 2, 3].
  • 2 <= 3 is true, so i becomes 1 and the array changes to [1, 2, 5, 4, 3].
  • Final pivot placement uses another slice assignment: @$arr[$i + 1, $high] = @$arr[$high, $i + 1], putting 3 at index 2 and producing [1, 2, 3, 4, 5].
  • quick_sort recurses only when $low < $high; the replay then summarizes the already-sorted left side [1, 2] and right side [4, 5] instead of expanding every base-case call.
  • The final print concatenates "[", join(", ", @arr), and a closing bracket string that includes the newline, producing [1, 2, 3, 4, 5].
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.