Design an algorithm for performing merge sort. Analyze its time efficiency; apply the same to sort the following number. 4 9 0 -1 6 8 9 2 3 12
Answer:-
Algorithm: Merge Sort
Apply the same to sort the following number. 4 9 0 -1 6 8 9 2 3 12
[4, 9, 0, -1, 6, 8, 9, 2, 3, 12]
[4, 9, 0, -1, 6] | [8, 9, 2, 3, 12]
[4, 9] | [0, -1, 6] | [8, 9] | [2, 3, 12]
[4, 9] | [-1, 0, 6] | [8, 9] | [2, 3, 12]
[-1, 0, 4, 6, 9] | [2, 3, 8, 9, 12]
The time complexity of the merge sort algorithm is O(n log n), where n is the number of elements in the array.