Shuttle sort
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, or shuttle sort, is a stable sorting algorithm that varies from bubble sort in that instead of repeatedly passing through the list from top to bottom, it passes alternately from top to bottom and then from bottom to top.
Complexity in Big O notation is O(n²) for a worst case, but becomes closer to O(n) if the list is mostly ordered at the beginning.
Implementation
sub cocktail_sort(@)
{
my @a = @_;
my ($left,$right) = (0,@#_);
while ($left < $right) {
foreach $i ($left..$right-1) {
($a[$i],$a[$i+1]) = ($a[$i+1],$a[$i]) if ($a[$i] > $a[$i+1]);
}
$right--;
foreach $i (reverse $left+1..$right) {
($a[$i],$a[$i-1]) = ($a[$i-1],$a[$i]) if ($a[$i] < $a[$i-1]);
}
$left++;
}
return @a;
}
