Merge Sort - Implementation in PHP

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

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 PHP implementation of Merge Sort algorithm:

<?php
#- Sort_Functions.php
#- Copyright (c) HerongYang.com. All Rights Reserved.
#-
function mergeSort(&$a, $fromIndex, $toIndex) {
   $b = array();
   for ($i=$fromIndex; $i<$toIndex; $i++) {
      $b[$i] = $a[$i];
   }
   mergeSortInternal($b, $a, $fromIndex, $toIndex);
}
function mergeSortInternal(&$a, &$b, $fromIndex, $toIndex) {
   if ($toIndex-$fromIndex<=1) {
      return;
   } else if ($toIndex-$fromIndex==2) {
      if (($a[$fromIndex])>$a[$toIndex-1]) {
         $b[$toIndex-1] = $a[$fromIndex];
         $b[$fromIndex] = $a[$toIndex-1];
      }
   } else {
      $iMiddle = intval(($toIndex-$fromIndex)/2) + $fromIndex;
      mergeSortInternal($b,$a,$fromIndex,$iMiddle);
      mergeSortInternal($b,$a,$iMiddle,$toIndex);
      $iLeft = $fromIndex;
      $iRight = $iMiddle;
      $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 ...
?>

Note that:

Here are the performance test results of mergeSort() function using PHP 5.6.

Array size: 10000
Average sorting time: 27.802 milliseconds
Number of tests: 1000
Performance: 2.7802 O(N) microseconds
Performance: 0.20923089848625 O(N*Log2(N)) microseconds
Performance: 0.00027802 O(N*N) microseconds

Array size: 20000
Average sorting time: 60.544 milliseconds
Number of tests: 1000
Performance: 3.0272 O(N) microseconds
Performance: 0.2118743658595 O(N*Log2(N)) microseconds
Performance: 0.00015136 O(N*N) microseconds

Array size: 30000
Average sorting time: 93.356 milliseconds
Number of tests: 1000
Performance: 3.1118666666667 O(N) microseconds
Performance: 0.20923382590678 O(N*Log2(N)) microseconds
Performance: 0.00010372888888889 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
Quicksort            20      42      76
Merge Sort           28      60      93
Insertion Sort     2213    9484   23329
Selection Sort     3580   14129   33808
Bubble Sort        6847   28427   66524

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

 Sort_Test.php - Sorting Performance Test

 Insertion Sort - Implementation in PHP

 Selection Sort - Implementation in PHP

 Bubble Sort - Implementation in PHP

 Quicksort - Implementation in PHP

Merge Sort - Implementation in PHP

 Heap Sort - Implementation in PHP

 Shell Sort - Implementation in PHP

 Sorting Algorithms Implementations in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB