• Data Structure and Algorithm - Merge Sort
  • Problem to Solve
  • Pseudocode
  • PHP Implementation
  • The End

#Data Structure and Algorithm - Merge Sort

In this tutorial, we will learn a simple sorting algorithm - Merge Sort.

#Problem to Solve

Given a list of numbers as shown below, please sort them in ascending order.

$numbers = [21,25,100,98,89,77];

Requirements:

• You are required to use Merge Sort algorithm when sorting the numbers.
• You are required to implement the algorithm in PHP language.

#Pseudocode

Merge Sort is a divide and conquer algorithm. It works by continually splitting a list in half until both halves are sorted, then the operation merge is performed to combine two lists into one sorted new list.

When splitting a list, we consider the list is sorted if it contains zero or one element.

Split:

Merge:

Pseudocode of Merge Sort algorithm can be written as follows:

PROCEDURE function mergeSort
   FOR each element of the master list indexed by i
 
       if ( i <= 1 ) return a
 
       var left = a[0] to a[i/2]
       var right = a[i/2+1] to a[i]
 
       left = mergeSort( left )
       right = mergeSort( right )
 
       return merge( left,right )
 
   END FOR
END PROCEDURE
 
PROCEDURE function mergeSort
    WHILE length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
 
    IF length(left) > 0
        append left to result
    END IF
 
    IF length(right) > 0
        append right to result
    END IF
 
    return result
END PROCEDURE

#PHP Implementation

As we can see, there are two procedures in this algorithm. This leads us to two PHP functions, where the first function(mergeSort) involves a recursion.

<?php
$arrayToSort = [21, 25, 100, 98, 89, 77];
 
function mergeSort($data)
{
    if (count($data) <= 1) {
        return $data;
    }
 
    $left = array_slice($data, 0, intval((count($data) / 2)));
    $right = array_slice($data, intval(count($data) / 2));
 
    $left = mergeSort($left);
    $right = mergeSort($right);
 
    return merge($left, $right);
}
 
function merge($left, $right)
{
    $sorted = [];
 
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] < $right[0]) {
            $firstLeft = array_shift($left);
            $sorted[] = $firstLeft;
        } else {
            $firstRight = array_shift($right);
            $sorted[] = $firstRight;
        }
    }
 
    for ($i = 0; $i < count($left); $i++)
        $sorted[] = $left[$i];
 
    for ($i = 0; $i < count($right); $i++)
        $sorted[] = $right[$i];
 
    return $sorted;
}
 
print_r(mergeSort($arrayToSort));
 
// Output:
/*
Array
(
    [0] => 21
    [1] => 25
    [2] => 77
    [3] => 89
    [4] => 98
    [5] => 100
)
*/

We have followed the pseudocode strictly to implement the algorithm in PHP. The only parts that we want to highlight are a couple of built-in PHP array functions:

• array_slice: It extracts a slice of the array. This function is handy when we want to a certain part of the array.
• array_shift: It remove an element from the beginning of an array. This function is handy when we want to remove the first element of the array.

#The End

If you like our post, please follow us on Twitter and help spread the word. We need your support to continue. If you have questions or find our mistakes in above tutorial, do leave a comment below to let us know.