Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm
Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show its computing time is O(n logn). Merge sort 10, 5, 7, 6, 1, 4, 8, 3, 2, 9
Sorted list: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Merge sort satisfies \(T(n) = 2T(n/2) + cn\), which gives \(O(n\log n)\).
Divide (mid = ⌊(low + high)/2⌋, positions 1 to 10):
[10, 5, 7, 6, 1, 4, 8, 3, 2, 9]
[10, 5, 7, 6, 1] [4, 8, 3, 2, 9]
[10, 5, 7] [6, 1] [4, 8, 3] [2, 9]
[10, 5] [7] [6] [1] [4, 8] [3] [2] [9]
[10] [5] [4] [8]
Merge (bottom up):
[10] + [5] -> [5, 10]
[5, 10] + [7] -> [5, 7, 10]
[6] + [1] -> [1, 6]
[5, 7, 10] + [1, 6] -> [1, 5, 6, 7, 10]
[4] + [8] -> [4, 8]
[4, 8] + [3] -> [3, 4, 8]
[2] + [9] -> [2, 9]
[3, 4, 8] + [2, 9] -> [2, 3, 4, 8, 9]
[1, 5, 6, 7, 10] + [2, 3, 4, 8, 9]
-> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Algorithm:
MergeSort(low, high):
if low < high:
mid = (low + high) / 2
MergeSort(low, mid)
MergeSort(mid + 1, high)
Merge(low, mid, high) // merge two sorted halves
Computing time: merging two sorted lists with a total of \(n\) elements takes at most \(n\) comparisons, i.e. \(cn\). So
\[T(n) = 2T(n/2) + cn,\quad T(1) = a\]
Substituting repeatedly, with \(n = 2^{k}\):
\[T(n) = 4T(n/4) + 2cn\]
\[= 2^{k}T(1) + k\,cn\]
\[= an + cn\log_2 n\]
Hence \(T(n) = O(n\log n)\) in the best, average and worst cases. It needs \(O(n)\) extra space for merging.
Log in or create a free account to answer this question.