Explanation

• Concept: Merge sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves.
• Process: Merge sort recursively splits the array into halves until each subarray contains a single element, then merges the subarrays to produce a sorted array.
• Steps:
  • Divide the array into two halves.
  • Recursively sort each half.
  • Merge the sorted halves to produce the sorted array.
• Efficiency: Merge sort has a time complexity of O(n log n) for all cases, making it efficient for large datasets. However, it requires additional memory space for the temporary arrays used during merging.

Python Implementation

      
          from typing import List

def merge_sort(arr: List[int]) -> List[int]:
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = merge_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [64, 25, 12, 22, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 12, 22, 11] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [11, 12, 22, 25, 64]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [64, 25, 22, 12, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 22, 12, 11] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [64, 25, 12, 22, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [11, 12, 22, 25, 64], "expected": [11 ,12, 22, 25, 64]},
        {"input": [64, 25, 22, 12, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = merge_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()