Problem Statement
Explain Merge Sort algorithm. How does it work and what are its advantages and disadvantages?
Explanation
Merge Sort is a divide-and-conquer sorting algorithm that recursively divides the array into halves, sorts them, and merges the sorted halves back together. It guarantees O of n log n time complexity for all cases.
The algorithm works in three main steps. First, divide the array into two halves by finding the middle index. Continue dividing recursively until each subarray has one element, which is inherently sorted. Second, conquer by recursively sorting the two halves. The base case is when a subarray has one or zero elements. Third, merge the two sorted halves back together by comparing elements from both halves and placing them in correct order.
The merge operation works by maintaining two pointers, one for each sorted half. Compare elements at both pointers and place the smaller element in the result array. Move the pointer of the array from which element was taken. Continue until all elements from both halves are merged. Time complexity is O of n for merging as we process each element once.
Time complexity analysis shows that dividing the array creates log n levels because we halve the array each time. At each level, we perform O of n work to merge all subarrays at that level. Total time is O of n log n for all cases, whether best, average, or worst. Space complexity is O of n because we need temporary arrays to store the merged results. This is the main disadvantage as it requires extra space proportional to array size.
Advantages of Merge Sort include guaranteed O of n log n time complexity regardless of input, making it predictable and reliable. It is a stable sort preserving the relative order of equal elements, which is important for multi-key sorting. It works well with linked lists where no extra space is needed for merging. It is suitable for external sorting when data does not fit in memory. The algorithm is parallelizable as independent subarrays can be sorted concurrently.
Disadvantages include O of n space complexity requiring extra memory for temporary arrays, which can be prohibitive for large datasets. It is slower than Quick Sort in practice for arrays due to the overhead of copying elements. It cannot take advantage of nearly sorted data unlike Insertion Sort. It is not an in-place algorithm, requiring additional space allocation.
Merge Sort is preferred when you need guaranteed O of n log n performance, when stability is required, when dealing with linked lists, or when the dataset is too large to fit in memory requiring external sorting.