Merge sort is a sorting algorithm that uses the Divide, Conquer, and Combine algorithm paradigm. It uses a function merge which combines the sub-arrays to form a sorted array. While the merge sort algorithm recursively divides the list into smaller lists, the merge algorithm conquers the list to sort the elements in the individual lists.Finally, the smaller lists are merged to form one list.
MERGE_SORT( A, BEG, END ) :
Here A is an unsorted array. BEG is the lower bound and END is the upper bound.
Step I : If (BEG < END) Then
Step II : Set MID = (BEG + END) / 2
Step III : Call Merge Sort (A, BEG, MID)
Step IV : Call Merge Sort (A, MID + 1, END)
Step V : Call Merge (A, BEG, MID, END)
[End of If]
Step VI : Exit.
MERGE ( A, BEG, MID, END ) :
Here A is an unsorted array. BEG is the lower bound, END is the upper bound and MID is the
middle value of array. B is an empty array.
Step I : Repeat For I = BEG to END
Step II : Set B[I] = A[I] [Assign array A to B]
[End of For Loop]
Step III : Set I = BEG, J = MID + 1, K = BEG
Step IV : Repeat While (I <= MID) and (J <= END)
Step V : If (B[I] <= B[J]) Then [Assign smaller value to A]
Step VI : Set A[K] = B[I]
Step VII : Set I = I + 1 and K = K + 1
Step VIII : Else
Step IX : Set A[K] = B[J]
Step X : Set J = J + 1 and K = K + 1
[End of If]
[End of While Loop]
Step XI : If (I <= MID) Then [Check whether first half
Step XII : Repeat While (I <= MID) has exhausted or not]
Step XIII : Set A[K] = B[I]
Step XIV : Set I = I + 1 and K = K + 1
[End of While Loop]
Step XV : Else
Step XVI : Repeat While (J <= END)
Step XVII : Set A[K] = B[J]
Step XVIII : Set J = J + 1 and K = K + 1
[End of While Loop]
[End of If ]
Step XIX : Exit.
Explained using figure :-
Merge sort and Quick sort are widely used for online sorting where data may not be present as one big chunk in the beginning but may be available in pieces.
Myprogworld 