#!/usr/bin/perl

# implementation of the merge sort algorithm for demonstration and testing
# purposes.
#
# written and © by Jan 'jast' Krüger, 2003.
# See the enclosed file COPYING for license details.

use warnings;
use strict;

# candy initialisation
my $swaps = 0;
my $compares = 0;
my $c2 = "\x1b[1;32m";
my $c1 = "\x1b[1;31m";
my $c0 = "\x1b[0;37m";

sub swap
{
	my ($ar, $a, $b) = @_[0..2];
	my $t;
	$t = $ar->[$b];
	$ar->[$b] = $ar->[$a];
	$ar->[$a] = $t;
	$swaps+=3;
}

sub cmpaa
{
	my ($ar, $a, $b) = @_[0..2];
	$compares++;
	$ar->[$a] cmp $ar->[$b];
}

sub cmpav
{
	my ($ar, $a, $b) = @_[0..2];
	$compares++;
	$ar->[$a] cmp $b;
}

sub cmpvv
{
	$compares++;
	$_[0] <=> $_[1];
}

sub mergesort
{
	my ($l, $r, $array) = @_[0..2];

	return if(cmpvv($l, $r) >= 0);
	mergesort($l, int(($r+$l)/2), $array);
	mergesort(int($r+$l)/2+1, $r, $array);

	# don't know whether this is the "official" merging technique.
	# i do know that it sucks. it's basically a somewhat optimised insertion
	# sort...
	my ($oswp, $ocmp) = ($swaps, $compares);
	my ($sl, $sr) = ($l, int(($r+$l)/2+1));
	my ($v, $s);
	while(cmpvv($sr, $r) < 1) {
		# merge an element of the right half into the left
		$sl++ until(cmpaa($array, $sl, $sr) >= 0);
		last if(cmpvv($sl, $sr) == 0);
		$v = $array->[$sr]; $swaps++;
		$s = $sr;
		while(cmpvv($s, $sl) > 0) {
			$array->[$s] = $array->[$s-1];
			$swaps++;
			$s--;
		}
		$array->[$s] = $v; $swaps++;
		$sr++;
	}

	# and colourfulness again
	printf "(%3sa, %3sc)\t", ($swaps-$oswp), ($compares-$ocmp);
	print join(' ', @$array[0..($l-1)]) .' ' if($l > 0);
	print $c2 . join(' ', @$array[$l..$r]) . "$c0 ";
	print join(' ', @$array[($r+1)..(@$array-1)]) if($r+1 < @$array);
	print "\n";
}

sub main {
	my @array = split(//, 'abcdefgEXAMPLE5732471238');
#	my @array = split(//, 'EXAMPLE');

	print "start:\t\t". join(' ', @array) ."\n";
	mergesort(0, @array-1, \@array);
	printf "%4sa (=> \%ds), \%sc insgesamt.\n", $swaps, ($swaps/3), $compares;
	print "explanation: a = assigns, s = swaps, c = compares, ${c2}just merged$c0\n";
}

main();
