use strict; use warnings; use Time::HiRes qw(time); # ------------------------------------------------------------------- # load_file # Purpose: # Read non-empty integer lines from an input file. # Parameters: # $fileSpec - path of the input file to read. # Returns: # An array of the parsed integers. # Side effects: # Opens and closes the input file and prints read progress. # ------------------------------------------------------------------- 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; } # ------------------------------------------------------------------- # save_file # Purpose: # Write each integer in an array to its own output-file line. # Parameters: # $values - array reference containing the integers to write. # $fileSpec - output file path. # Returns: # No value. # Side effects: # Creates and closes the output file and prints progress. # ------------------------------------------------------------------- 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"; } # ------------------------------------------------------------------- # merge # Purpose: # Merge two sorted arrays into one sorted array. # Parameters: # $left - reference to the first sorted input array. # $right - reference to the second sorted input array. # Returns: # A reference to a new array containing all values in order. # Side effects: # Removes values from the input arrays as it merges them. # ------------------------------------------------------------------- sub merge { my ($left, $right) = @_; my @result = (); while(@$left > 0 && @$right > 0) { if($left->[0] <= $right->[0]) { push(@result, shift(@$left)); } else { push(@result, shift(@$right)); } } push(@result, @$left); push(@result, @$right); return \@result; } # ------------------------------------------------------------------- # merge_sort # Purpose: # Recursively divide an array, sort each half, and merge them. # Parameters: # $values - reference to the array to sort. # Returns: # A reference to an array containing the values in ascending order. # Side effects: # Creates sorted subarrays without modifying the input array. # ------------------------------------------------------------------- sub merge_sort { my ($values) = @_; my @array = @$values; if( @array <= 1 ) { return $values; } my @left = (); my @right = (); my $middle = int(@array/2); for(my $i = 0; $i < @array; $i++) { if($i < $middle) { push(@left,$array[$i]); } else { push(@right,$array[$i]); } } my $leftsorted = merge_sort(\@left); my $rightsorted = merge_sort(\@right); return merge($leftsorted, $rightsorted); } # ------------------------------------------------------------------- # do_sort # Purpose: # Time the merge sort and save its sorted result. # Parameters: # $values - reference to the array to sort. # Returns: # Elapsed time in seconds. # Side effects: # Prints progress and writes the sorted values to the output file. # ------------------------------------------------------------------- sub do_sort { print("SORTING ELEMENTS..."); my ($values) = @_; my $startTime = time; my $count = scalar @$values; my $finalvalues = merge_sort($values); my $endTime = time; print("DONE.\n"); save_file($finalvalues, "D:/Sorting/Output_PERL.txt"); return $endTime - $startTime; } print "=========MERGESORT PERL=========\n"; my @values = load_file("D:/Sorting/Sorting_Input.txt"); my $elapsed = do_sort(\@values); print "==========RUN COMPLETE==========\n"; printf "MERGESORT TOOK %.6f SECONDS.\n", $elapsed; print "================================\n";