Home > Sort algorithms > Merge sort algorithm – PHP implementation

Merge sort algorithm – PHP implementation

Heapsort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.


  • Worst case: O(n logn)
  • Average case: O(n logn)
  • Best case: O(n logn)

PHP implementation (a special class for merge sorting):

class mergeSort {
     * splitting the array recursively until has max two elements
     * merging and sorting recursively until sorted array is built
     * @param type $array
     * @return array Sorted input array
    public function sort($array) {
        //if array has 1 element return that element
        if ($count<=1)
            return $array;
        //split array and build left and right arrays
        for ($i=0;$i<$mid;$i++) {
        for ($i=$mid;$imerge($this->sort($left),$this->sort($right));
     * merge left and right arrays sorting elements
     * @param array $left
     * @param array $right
     * @return array
    private function merge($left,$right) {
        //compare first element from left with first element from right
        //add the lowest to $sorted and erase it from parent array
        while (count($left)>0 && count($right)>0) 
            if ($left[0]<$right[0]) {
            } else {
        //after one of right and left arrays is empty is added elements from
        //remaining to $sorted
        for ($i=0;$i<count($left);$i++) 
        for ($i=0;$i<count($right);$i++) 
        return $sorted;


  1. Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  2. Algorithms – Robert Sedgewick
  3. http://en.wikipedia.org/wiki/Merge_sort
Categories: Sort algorithms Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: