The mergesort algorithm
closely follows the divide-and-conquer paradigm. Generally, Merge Sort
is considered to be one of the best internal sorting methods. If the data
is too large to be accommodated all at once in the memory then one has
to use external sorting methods. In external sorting methods small blocks
of data are loaded into the memory, sorted using an internal sorting method
and written out to a tape or disk. Sorted parts are then merged using variations
of the merging algorithm discussed below:
Mergesort(A,p,r){
if p < r
then q <- |(p+ r)/2|
Mergesort(A,p,q)
Mergesort(A,q+1,r)
Merge(A,p,q,r)
}
To sort the entire sequence
A, Mergesort(A,1,length[A]) is called where length[A]=N.
Mergesort works by splitting
the list into two halves and then sorting each half recursively. Mergesort
may be considered to be a tree based algorithm and over here it is executed
in a depth first manner. For the above list the algorithm starts by handling
the merging of elements as follows (the trend in which the sublists are
being considered):
1. First, elements 1 and 2
are handled.
2. Then, elements from 0 through
2 are handled (note the black items indicating the border elements).
3. Then, elements 3 and 4
are handled. After this, elements 5 and 6.
4. Then, elements 3 through
6 are handled.
Subsequently, elements 0 through
6 are handled and so on until elements 0 to 14 are handled.
The Merge algorithm takes two
sorted lists and merges them to give a sorted list. It assumes the existence
of a temporary merge space whose current contents are shown on the upper
canvas of the above applet. Mereg takes the the smaller of the first elements
of the two lists and places it into the merge space. When either input
list is exhausted, the remainder of the other list is copied to the merge
space. The sorted sublist is then copied back from the merge space into
the appropriate indices.
Merge Sort algorithm uses
the process of merging two sorted lists recursively to accomplish the sorting
of an unsorted list. Firstly, two sorted lists of length M and N respectively
can be merged in O(M+N) time. If the lists have the same size N then the
time will be O(2*N) or O(N).
First, each individual element
of the list is considered as a 1-element sorted list. The merge algorithm
is then used N/2 times to merge pairs of elements into sorted lists of
length 2. This will produce N/2 sorted lists each of length 2. It takes
N/2 comparisons to accomplish this. Pairs of 2-element lists are then merged
to produce N/4 sorted lists each of length 4. In this case there are N/4
merge operations each taking at most 4 comparisons. This process continues
until we have two sorted lists of size N/2 and we merge them in O(N) time.
There are log(N) levels of merging. Hence, Merge Sort has a worst-case
complexity of O(N*log(N)).
