Merge Sort - Implementation in Perl

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟Sorting Algorithms Implementations in Perl

∟Merge Sort - Implementation in Perl

This section provides a tutorial on how to implement the Merge Sort algorithm in Perl.

Merge Sort is a complex and fast sorting algorithm that repeatedly divides an un-sorted section into two equal sub-sections, sorts them separately and merges them correctly.

The basic idea of Merge Sort algorithm can be described as these steps:

1. Divide the data elements into two sections with equal number of elements.

2. Sort the two sections separately.

3. Merge the two sorted sections into a single sorted collection.

Obviously, this is a recursive idea, where a problem is divided into smaller problems. And the division will be repeated to make the smaller problems even smaller, until they are smaller enough so that the solutions are obvious.

Here is my Perl implementation of Merge Sort algorithm:

#- Sort_Function.pl
#- Copyright (c) 2015 HerongYang.com. All Rights Reserved.
#-
sub mergeSort {
   my ($a, $fromIndex, $toIndex) = @_;
   my @b = ();
   for ($i=$fromIndex; $i<$toIndex; $i++) {
      $b[$i] = $a->[$i];
   }
   mergeSortInternal(\@b, $a, $fromIndex, $toIndex);
}
sub mergeSortInternal {
   my ($a, $b, $fromIndex, $toIndex) = @_;
   if ($toIndex-$fromIndex<=1) {
      return;
   } elsif ($toIndex-$fromIndex==2) {
      if (($a->[$fromIndex])>$a->[$toIndex-1]) {
         $b->[$toIndex-1] = $a->[$fromIndex];
         $b->[$fromIndex] = $a->[$toIndex-1];
      }
   } else {
      my $iMiddle = int(($toIndex-$fromIndex)/2) + $fromIndex;
      mergeSortInternal($b,$a,$fromIndex,$iMiddle);
      mergeSortInternal($b,$a,$iMiddle,$toIndex);
      my $iLeft = $fromIndex;
      my $iRight = $iMiddle;
      my $i = $fromIndex;
      while ($iLeft<$iMiddle && $iRight<$toIndex) {
         if (($a->[$iLeft])>$a->[$iRight]) {
            $b->[$i] = $a->[$iRight];
            $iRight++;
         } else {
            $b->[$i] = $a->[$iLeft];
            $iLeft++;
         }
         $i++;
      }
      while ($iLeft<$iMiddle) {
         $b->[$i] = $a->[$iLeft];
         $iLeft++;
         $i++;
      }
      while ($iRight<$toIndex) {
         $b->[$i] = $a->[$iRight];
         $iRight++;
         $i++;
      }
   }
}

# Functions for other sorting algorithms ...

#- End
  1;

Note that:

Method mergeSort() is a wrapper of the real sorting method: mergeSortInternal().
Array b[] is created to help merging the two sorted sections back into a single sorted collection.

Here are the performance test results of mergeSort() function using Perl 5.18

Array size: 10000
Average sorting time: 47.7131103515625 milliseconds
Number of tests: 10
Performance: 4.77131103515625 O(N) microseconds
Performance: 0.359076935056148 O(N*Log2(N)) microseconds
Performance: 0.000477131103515625 O(N*N) microseconds

Array size: 20000
Average sorting time: 100.350317382813 milliseconds
Number of tests: 10
Performance: 5.01751586914063 O(N) microseconds
Performance: 0.351176992918922 O(N*Log2(N)) microseconds
Performance: 0.000250875793457031 O(N*N) microseconds

Array size: 30000
Average sorting time: 152.508984375 milliseconds
Number of tests: 10
Performance: 5.0836328125 O(N) microseconds
Performance: 0.341810256287099 O(N*Log2(N)) microseconds
Performance: 0.000169454427083333 O(N*N) microseconds

Here is the comparison of mergeSort() performance with other sorting functions.

Array Size        10000   20000   30000   100000   200000   300000
----------        -----   -----   -----   ------   ------   ------
JDK Arrays.sort                               25       66      112
PHP sort()            3       7      13       75
Perl sort()          11      22      36      171
Quicksort            20      46      75
Merge Sort           48     100     153
Insertion Sort     4125   16015   37098
Selection Sort     8054   31249   68985
Bubble Sort       19344   78360  177353