use strict;
use warnings;
use Time::HiRes qw(time);

my $Heaps = 0;
my $Insertions = 0;
my $Intros = 0;

sub load_file {
	print "READING INPUT FILE...";
	my ($fileSpec) = @_;
	open my $input_file, '<', $fileSpec or die "Cannot open $fileSpec: $!";
	my @values = map {chomp; $_} grep {/\S/} <$input_file>;
	close $input_file;
	print "DONE.\n";
	return @values;
}

sub save_file {
	print "SAVING OUTPUT FILE...";
	my ($values, $fileSpec) = @_;
	open my $output_file, '>', $fileSpec or die "Cannot create $fileSpec: $!";
	print {$output_file} "$_\n" for @$values;
	close $output_file or die "Cannot close $fileSpec: $1";
	print "DONE.\n";
}

sub sift_down {
	my ($values, $root, $start, $end) = @_;
	while ($start + 2 * ($root - $start) + 1 < $end) {
		my $child = $start + 2 * ($root - $start) + 1;
		$child++ if $child + 1 < $end && $values->[$child] < $values->[$child + 1];
		return if $values->[$root] >= $values->[$child];
		@$values[$root, $child] = @$values[$child, $root];
		$root = $child;
	}	
}

sub heap_sort {
	$Heaps++;
	my ($values, $start, $end) = @_;
	sift_down($values,$_,$start,$end) for reverse 0 .. int(@$values / 2) - 1;
	for(my $last = $end - 1; $last > $start; $last--) {
		@$values[$start, $last] = @$values[$last, $start];
		sift_down($values, $start, $start, $last);
	}
}

sub insertion_sort {
	$Insertions++;
	my ($values, $start, $end) = @_;
	for(my $index = $start; $index < $ end; $index++) {
		my $value = @$values[$index];
		my $pos = $index - 1;
		while ($pos >= $start && $values->[$pos] > $value) {
			$values->[$pos + 1] = $values->[$pos];
			$pos--;
		}
		$values->[$pos + 1] = $value;
	}
}

sub partition {
	my ($values, $start, $end) = @_;
	my $left = $start;
	my $right = $end - 1;
	my $pivot = $values->[$start + ($end - $start) / 2];
	while ($left <= $right) {
		while($values->[$left] < $pivot) { $left++; }
		while($values->[$right] > $pivot) { $right--; }
		if($left <= $right) {
			@$values[$left, $right] = @$values[$right, $left];
			$left++;
			$right--;
		}
	}
	return $left;
}

sub intro_sort {
	$Intros++;
	my ($values, $start, $end, $maxdepth) = @_;
	my $length = $end - $start;
	return if ($length <= 1);
	if ($length < 16) { insertion_sort($values, $start, $end); }
	elsif ($maxdepth <= 0) { heap_sort($values, $start, $end); }
	else {
		my $part = partition($values, $start, $end);
		intro_sort($values, $start, $part, $maxdepth - 1);
		intro_sort($values, $part, $end, $maxdepth - 1);
	}	
}

sub perform_sort {
	print("SORTING ELEMENTS...");
	my ($values) = @_;
	my $startTime = time;
	my $count = scalar @$values;
	my $maxdepth = $count > 1 ? log2($count) * 2 : 0;
	intro_sort($values, 0, $count, $maxdepth);
	my $endTime = time;
	print("DONE.\n");
	return $endTime - $startTime;
}

sub log2 {
	my ($val) = @_;
	my $num = 0;
	while ($val > 0) {
		$val = $val / 2;
		$num++;
	}
	return $num;
}

print "=========INTROSORT PERL=========\n";
my @values = load_file("D:/Sorting/Sorting_Input.txt");
my $elapsed = perform_sort(\@values);
save_file(\@values, "D:/Sorting/Output_PERL.txt");
print "==========RUN COMPLETE==========\n";
printf "INTROSORT TOOK %.6f SECONDS.\n", $elapsed;
print "================================\n";
print "SORT CALLED | TIMES\n";
print "------------+-------------------\n";
printf "Intro       | %d\n", $Intros;
printf "Insertion   | %d\n", $Insertions;
printf "Heap        | %d\n", $Heaps;
print "--------------------------------\n";