Merge Sort is a divide-and-conquer algorithm that divides the array into
smaller pieces, sorts each piece, and then merges them back together.
Time Complexity
Best Case: O(n log n) - Even in the best case, the array needs to be split
down and merged back, requiring n log n operations.
Average Case: O(n log n) - This is the standard time complexity for merge
sort, as each split divides the array in half.
Worst Case: O(n log n) - The worst case time complexity remains the same,
as the divide and merge operations are consistent regardless of the
input distribution.
Space Complexity: O(n) - This is because merge sort requires additional space
to store the temporary arrays used during the merge step. The space is used
to hold the two halves that are being merged, and this space adds up to n for
all levels of the recursion.
Merge Sort is a divide-and-conquer algorithm that divides the array into smaller pieces, sorts each piece, and then merges them back together.
Time Complexity
Best Case: O(n log n) - Even in the best case, the array needs to be split down and merged back, requiring n log n operations.
Average Case: O(n log n) - This is the standard time complexity for merge sort, as each split divides the array in half.
Worst Case: O(n log n) - The worst case time complexity remains the same, as the divide and merge operations are consistent regardless of the input distribution.
Space Complexity: O(n) - This is because merge sort requires additional space to store the temporary arrays used during the merge step. The space is used to hold the two halves that are being merged, and this space adds up to n for all levels of the recursion.