Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Perl DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.pl 
use strict; use warnings;
my @arr = (5, 1, 4, 2, 8);
for (my $i = 1; $i < @arr; $i++) {
	my $key = $arr[$i];
	my $j = $i - 1;
	while ($j >= 0 && $arr[$j] > $key) {
		$arr[$j + 1] = $arr[$j];
		$j--;
	}
	$arr[$j + 1] = $key;
}
print "[" . join(", ", @arr) . "]
";

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • my @arr = (5, 1, 4, 2, 8) declares the pinned Perl array with the @ sigil.
  • The outer loop is indexed: for (my $i = 1; $i < @arr; $i++). In that loop bound, @arr is in scalar context, so it means the array length.
  • Each pass copies the current value into a scalar key with my $key = $arr[$i].
  • my $j = $i - 1 starts the scan at the previous slot in the sorted prefix.
  • The while guard is ($j >= 0 && $arr[$j] > $key): it checks the left bound first, then uses Perl's numeric > comparison.
  • Shifting is an in-place array assignment: $arr[$j + 1] = $arr[$j].
  • After each shift, $j-- moves left; once the loop stops, $arr[$j + 1] = $key writes the saved key into the open slot.
  • The trace starts from [5, 1, 4, 2, 8].
  • With key 1, 5 shifts right and the array becomes [1, 5, 4, 2, 8].
  • With key 4, 5 shifts right and the array becomes [1, 4, 5, 2, 8].
  • With key 2, 5 and 4 shift right and the array becomes [1, 2, 4, 5, 8].
  • The final key 8 needs no shift, so the sorted array stays [1, 2, 4, 5, 8].
  • The final print concatenates "[", join(", ", @arr), and a closing bracket string that includes the newline, printing [1, 2, 4, 5, 8].
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.