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

• 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 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
```