Space Complexity
The Space Complexity is used for measure the amount of the memory an algorithm uses in relation to the size of the input. It includes both the Space Needed for the input itself and any additional space used by the algorithm.
Space Complexity Analysis
Input Space
The array to be sorted occupies O(n) space, where n is the number of eleents.
Auxiliary Space
Merge sort uses additional space for temporary arrays during the merge process. Each level of recursions requires merging arrays, so the total auxiliary space is O(n).
Example: –
We have Initial Array: –
[38, 27, 43, 3, 9, 82, 10]
1. Divide Phase
- Split Into [38, 27, 43, 3] and [9, 82, 10].
- Further split into [38, 27], [43, 3], [9] and [82,10].
- Continue until individual elements are isolated.
2. Conquer and Combine Phase
- Firstly, Merge [38] and [2] into [27, 38].
- Merge [43] and [3] into [3, 43].
- Merge resulting arrays [27, 38] and [3, 43].
- Simultaneously, merge [82] and [10] into [10, 82], and then merge with [9].