Sorting

Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.pl 
use strict; use warnings;
sub merge_sort {
	my @values = @_;
	return @values if @values <= 1;
	my $mid = int(@values / 2);
	my @left = merge_sort(@values[0 .. $mid - 1]);
	my @right = merge_sort(@values[$mid .. $#values]);
	my @merged;
	while (@left && @right) {
		push @merged, ($left[0] <= $right[0]) ? shift @left : shift @right;
	}
	return (@merged, @left, @right);
}

my @arr = merge_sort(5, 1, 4, 2, 8);
print "[" . join(", ", @arr) . "]
";

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

  • Time: O(n log n)
  • Space: O(n)
  • Stable: yes

Implementation notes

  • sub merge_sort receives its input as the argument list @_, then copies it into my @values = @_.
  • Perl arrays use the @ sigil here: @values, @left, @right, @merged, and the final @arr.
  • The base case is return @values if @values <= 1; in that numeric comparison, @values is in scalar context, so it means the list length.
  • my $mid = int(@values / 2) uses integer truncation to split the current list.
  • The recursive calls use Perl slice syntax: @values[0 .. $mid - 1] for the left half and @values[$mid .. $#values] for the right half.
  • The checked input is passed as a list in my @arr = merge_sort(5, 1, 4, 2, 8).
  • The trace shows the first split as left [5, 1] and right [4, 2, 8].
  • Recursive calls return sorted lists, so the replay then has left [1, 5] and right [2, 4, 8].
  • my @merged holds the output during the merge.
  • The merge loop runs while both halves still have elements: while (@left && @right).
  • The comparison is numeric and stable on ties: ($left[0] <= $right[0]) ? shift @left : shift @right.
  • shift removes the chosen front value from @left or @right, and push @merged, ... appends it to the merged result.
  • return (@merged, @left, @right) appends whichever half still has leftover values after the loop.
  • The final replayed merge returns [1, 2, 4, 5, 8].
  • The final print concatenates "[", join(", ", @arr), and a closing bracket string that includes the newline, producing [1, 2, 4, 5, 8].
divide and conquer Each recursive call solves a smaller sorted subproblem.
merge step Two sorted halves are combined by repeatedly taking the smaller front item.