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.
Algorithm:

  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.

Performance:

  • 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
        $count=count($array);
        if ($count<=1)
            return $array;
        //split array and build left and right arrays
        $mid=(int)$count/2;
        $left=array();
        $right=array();
        for ($i=0;$i<$mid;$i++) {
            $left[]=$array[$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) {
        $sorted=array();
        //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]) {
                $sorted[]=$left[0];
                array_shift($left);
            } else {
                $sorted[]=$right[0];
                array_shift($right);
            }
        //after one of right and left arrays is empty is added elements from
        //remaining to $sorted
        for ($i=0;$i<count($left);$i++) 
            $sorted[]=$left[$i];
        for ($i=0;$i<count($right);$i++) 
            $sorted[]=$right[$i];
        return $sorted;
    }
}

Bibliography:

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