Monday, Dec 11th

Last update12:59:40 PM GMT

Merge Sort

Write e-mail
Merge SortMerge Sort is a comparison-based sorting algorithm, based on the popular Divide-&-Conquer approach of sorting algorithms, which involve the following steps: 
  1. Divide: Divide the array of the size N into two sequences of size N/2, unless N=1 since at that point array can’t be further divided.
  2. Conquer: Sort the two sequences recursively, using the merge sort. Since at N=1, the further division is not possible, therefore we have just two sibling sequences each of size 1. And they don’t need to be sorted.
  3. Combine: Combine the two sorted sequences to form another sorted sequence. While merging the two sequences, the sorted order needs to be maintained in the final result sequence. This is made sure, by comparing the top elements of both sequences (assuming that smallest element is placed on the top in a sequence). The smaller one is placed on the top of the resultant array, and the element is removed from the corresponding sequence (In terms of array, the sequence array top index is updated to next index).

Merge Sort Algorithm 

argaiv1865

function mergeSort(arr)
 
if length(arr) ≤ 1
    return arr
var leftArr, rightArr, resultArr
mid = length(arr) / 2
for each x in arr up to mid
    add x to leftArr
for each x in m after mid
    add x to rightArr
leftArr = merge_sort(leftArr)
rightArr = merge_sort(rightArr)
resultArr = merge(leftArr, rightArr)
return resultArr

function merge(leftArr, rightArr)
 
var resultArr
while length(leftArr) > 0 or length(rightArr) > 0
    if length(leftArr) > 0 and length(rightArr) > 0
        if first(leftArr) ≤ first(rightArr)
            append first(leftArr) to resultArr
            leftArr = rest(leftArr)
        else
            append first(rightArr) to resultArr
            rightArr = rest(rightArr)
    else if length(leftArr) > 0
        append leftArr to resultArr
    else if length(rightArr) > 0
        append rightArr to resultArr
end while
return resultArr

Analysis

It can be easily seen that the sorting time represented as T(n) can be calculated as the sum of the above two methods time. For an array of size of N, the mergeSort has time as T(N) = 2T(N/2) + N, since the merge method has N iterations. And since we perform two merge sorts on half the size, therefore 2T(N/2). The merge sort has worst case and average performance as O(n log n) for the array of size n.

The most common implementation of the merge sort is not in place and therefore, it requires the memory size of the input allocated for storing the output. The in-place sorting implementation is possible but is very complicated, and hardly offers any performance gain in practise, even if the algorithm runs in O(n log n) time.

Comparison with other sort algorithms

As compared to quicksort, merge sort is much more efficient if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages where sequentially accessed data structures are very common, like Lisp. Unlike some (inefficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly.

Although heap sort has the same time bounds as merge sort, it requires only Ω(1) auxiliary space instead of merge sort's Ω(n), and is consequently often faster in practical implementations. Quicksort, however, is considered by many to be the fastest general-purpose sort algorithm in practice. Its average-case complexity is O(n log n), with a much smaller coefficient, in good implementations, than merge sort's, even though it is quadratic in the worst case. On the plus side, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it does not require Ω(n) auxiliary space (instead only Ω(1)), and the slow random-access performance of a linked list makes some other algorithms (such as quick sort) perform poorly, and others (such as heapsort) completely impossible.

In Java, the Arrays.sort() methods use mergesort and a tuned quicksort depending on the datatypes.


Share this post



Add comment

Please refrain from using slang or abusive language in the comments.
To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.


Security code
Refresh

Web Hosting