Merge Sort

 

MERGING:

The operation of sorting is closely related to the process of merging. The merging of two order table which can be combined to produce a single sorted table. This process can be accomplished easily by successively selecting the record with the smallest key occurring by either of the tables and placing this record in a new table.

MERGE SORT

If working on an array a of size n with entries a[0],..., a[n-1], then the obvious approach is to simply split the set of indices. That is, we split the array at item n=2 and consider the two sub-arrays a[0],...,a[(n-1)/2] and a[(n+1)/2],...,a[n-1]. This method has the advantage that the splitting of the collection into two collections of equal (or nearly equal) size at each stage is easy. However, the two sorted arrays that result from each split have to be merged together carefully to maintain the ordering. This is the underlying idea for a sorting algorithm called mergesort.

ALGORITHM:

PSEUDOCODE:

Else L=L+1

TEMP[L]=K[J]

J=J+1

Step 3: [Copy remaining unprocessed element in output area]

If I>=SECOND

Then repeat while J<=THIRD

L=L+1

TEMP[L]=K[J]

J=J+1

Else

Repeat while I< SECOND

L=L+1

TEMP[L]=K[I]

I=I+1

Step 4: [Copy the element into temporary vector into original area]

Repeat for I=1,2,…..L

K[FIRST-I+1]=TEMP[I]

Step 5: Exit

Step 1: [Initialize]

Set I = FIRST

Set J = SECOND

Set L = 0

Step 2: [Compare corresponding elements and output the smallest]

Repeat while I < SECOND & J < THIRD

If K[I] <= K[J],then L=L+1

TEMP [L]=K[I]

I=I+1

PROTOTYPE CODE:

mergesort(array a, int left, int right) {

if ( left < right ) {

mid = (left + right) / 2

mergesort(a, left, mid)

mergesort(a, mid+1, right)

merge(a, left, mid, right)

}

}

FUNCTIONING DIAGRAM:

COMPLEXITY ANALYSIS:

The total number of comparisons needed at each recursion level of mergesort is the number of items needing merging which is O(n), and the number of recursions needed to get to the single item level is O(log2 n), so the total number of comparisons and its time complexity is O(nlog2 n). This holds for the worst-case as well as the average case. Like Quicksort, it is possible to speed up mergesort by abandoning the recursive algorithm when the sizes of the sub-collections become small.

For arrays, 16 would once again be a suitable size to switch to an algorithm like Selection Sort. Note that, with Mergesort, for the special case when only the largest/smallest m << n items need to be found and sorted, rather than all n, there is no way to reduce the time complexity in the way it was possible with Heapsort and Quicksort. This is because the ordering of the required items only emerges at the very last stage after the large majority of the comparisons have already been carried out.