Explain the merge sort algorithm.

Merge Sort is a classic, efficient, and comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It divides the unsorted list into smaller sublists until each sublist contains a single element, which is inherently sorted. Then, it merges these sublists to produce new sorted sublists until there is only one sorted list remaining.

Key Talking Points:

• Divide and Conquer: Merge Sort splits the array into smaller subarrays until each subarray contains a single element.
• Stable Sort: Maintains the relative order of equal elements.
• Time Complexity:
  • Best, Worst, Average: O(n log n)
• Space Complexity: O(n) due to the need for a temporary array for merging.
• Not In-place: Requires additional space for merging.
• Recursive and Iterative Implementations: Merge Sort can be implemented recursively (more common) or iteratively.

Pseudocode:

function mergeSort(array):
    if length of array <= 1:
        return array

    mid = length of array / 2
    leftHalf = mergeSort(array[0:mid])
    rightHalf = mergeSort(array[mid:end])

    return merge(leftHalf, rightHalf)

function merge(left, right):
    result = []
    while left is not empty and right is not empty:
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0] from left
        else:
            append right[0] to result
            remove right[0] from right

    while left is not empty:
        append left[0] to result
        remove left[0] from left

    while right is not empty:
        append right[0] to result
        remove right[0] from right

    return result

NOTES:

Reference Table:

Follow-Up Questions and Answers:

1. What are the advantages of using Merge Sort over Quick Sort?

   • Answer: Merge Sort has a guaranteed time complexity of O(n log n) in the worst case, making it ideal for datasets where consistency is important. It is also stable, preserving the relative order of equal elements. Additionally, it performs well on linked lists as it requires less memory manipulation than arrays.

2. Can you implement Merge Sort in an iterative manner?

   • Answer: Yes, Merge Sort can be implemented iteratively by using a bottom-up approach, gradually merging arrays of increasing size.

3. Why is Merge Sort not suitable for in-place sorting?

   • Answer: Merge Sort requires additional space proportional to the size of the array being sorted to hold the temporary merged results, which makes it unsuitable for in-place sorting where extra space usage is a concern.