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) 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:

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

Table of Contents

 About This Book

 Introduction of Sorting Algorithms

 Java API for Sorting Algorithms

 Insertion Sort Algorithm and Java Implementation

 Selection Sort Algorithm and Java Implementation

 Bubble Sort Algorithm and Java Implementation

 Quicksort Algorithm and Java Implementation

 Merge Sort Algorithm and Java Implementation

 Heap Sort Algorithm and Java Implementation

 Shell Sort Algorithm and Java Implementation

 Sorting Algorithms Implementations in PHP

Sorting Algorithms Implementations in Perl

 Sort_Test.pl - Sorting Performance Test

 Insertion Sort - Implementation in Perl

 Selection Sort - Implementation in Perl

 Bubble Sort - Implementation in Perl

 Quicksort - Implementation in Perl

Merge Sort - Implementation in Perl

 Heap Sort - Implementation in Perl

 Shell Sort - Implementation in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB