Merge Sort Algorithm Assignment Help
The merge sort algorithm is based on the particular classical divide-and-conquer paradigm. This operates the following:
DIVIDE: Partition the n-element sequence to become sorted into two subsequences associated with n/2 elements each.
CONQUER: Sort the two subsequences recursively while using the merge sort.
COMBINE: Merge the two sorted subsequences associated with size n/2 every to produce the sorted sequence comprising n elements.
Merge Sort Algorithm Example
MERGE SORT (A, p, r) 1 if p 2 then q [ (p + r) / 2 ] 3 MERGE SORT(A, p, q) 4 MERGER SORT(A, q + 1, r) 5 MERGE(A, p, q, r)
Implementing Merge Sort:
There tend to be two basic fundamental methods to implement merge sort:
- In Place: Merging is performed along with just the actual input array
- Pro: Requires just the space required to contain the array
- Con: Requires longer in order to merge because if the next element is within the actual right side after that all the elements should be moved down.
- Double Storage: Merging is performed having a temporary array from the exact same size since the input array.
- Pro: Quicker compared to In position because the temp array retains the resulting array till each left as well as right sides tend to be merged into the temp array, then the temp array is appended within the input array.
- Con: The memory necessity is doubled.
Merge Sort Analysis:
The actual Double Memory Merge Sort runs O (N log N) for those cases, due to the Divide as well as Conquer approach.
T(N) = 2T(N/2) + N = O(N logN)