现在的位置: 首页 > 综合 > 正文

Algorithm of the Week: Merge Sort

2013年10月01日 ⁄ 综合 ⁄ 共 2233字 ⁄ 字号 评论关闭

Basically sorting algorithms can be divided into two main groups: those based on comparisons and those that are not. I already posted about some of the algorithms of the first group. Insertion sort, bubble sort and Shell sort are based on the comparison model.
The problem with these three algorithms is that their complexity is O(n2) so they are very slow.

So is it possible to sort a list of items by comparing their items faster than O(n2)? The answer is yes and here’s how we can do it.

The nature of those three algorithms mentioned above is that we almost compared each two items from initial list.

This, of course, is not the best approach and we don’t need to do that. Instead we can try to divide the list into smaller lists and then sort them. After sorting the smaller lists, which is supposed to be easier than sorting the entire initial list, we can
try to merge the result into one sorted list. This technique is typically known as “divide and conquer”.

Normally if a problem is too difficult to solve, we can try to break it apart into smaller sub-sets of this problem and try to solve them. Then somehow we can merge the results of the solved problems. 

Overview

Merge sort is a comparison model sorting algorithm based on the “divide and conquer” principle. So far so good, so let’s say we have a very large list of data, which we want to sort. Obviously it will be better if we divide the list into two sub-lists with
equal length and then sort them. If they remain too large, we can continue breaking them down until we get to something very easy to sort as shown on the diagram bellow.

The thing is that in some step of the algorithm we have two sorted lists and the tricky part is to merge them. However this is not so difficult.
We can start comparing the first items of the lists and than we can pop the smaller of them both and put it into a new list containing the merged (sorted) array.

Implementation

The good news is that this algorithm is fast, but not too difficult to implement and that sounds quite good from a developer’s point of view. Here’s the implementation in PHP. Note that every algorithm that follows the divide and conquer principles can be easily
implemented in a recursive solution. However recursion can be bitter so you can go for a iterative solution. Typically recursion is “replaced” by additional memory space in iterative solutions. Here’s a recursive version of merge sort.

01.$input array(6,
5, 3, 1, 8, 7, 2, 4);
02. 
03.function merge_sort($arr
04.
05.if (count($arr)
<= 1) {
06.return $arr
07.}
08. 
09.$left array_slice($arr,
0, (int)(
count($arr)/2)); 
10.$right array_slice($arr,
(int)(
count($arr)/2)); 
11.

抱歉!评论已关闭.