What is merge sort?

Merge Sort is a sorting algorithm based on the "divide and conquer" principle. It recursively divides the array into two halves, sorts each half, and then merges the sorted halves into one sorted array.

Main steps:

1. Division: If the array contains more than one element, it is divided into two subarrays of approximately equal size.
2. Recursive sorting: Merge sort is called recursively for each of the two subarrays.
3. Merging: The sorted subarrays are merged into one sorted array.

def merge_sort(arr):
    # Base case: if the array contains 0 or 1 element, it is already sorted
    if len(arr) <= 1:
        return arr

    # Divide the array in half
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # Recursively sort both halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # Merge the sorted halves
    return merge(left_half, right_half)

def merge(left, right):
    # Initialize empty result and pointers
    result = []
    i = 0  # Pointer for the left half
    j = 0  # Pointer for the right half

    # Compare elements from both halves and add the smallest to the result
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Add remaining elements from the left half (if any)
    while i < len(left):
        result.append(left[i])
        i += 1

    # Add remaining elements from the right half (if any)
    while j < len(right):
        result.append(right[j])
        j += 1

    return result

# Example usage
# unsorted_list = [12, 11, 13, 5, 6, 7]
# sorted_list = merge_sort(unsorted_list)
# print(sorted_list) # [5, 6, 7, 11, 12, 13]

Algorithm complexity:

Operation	Worst-case time complexity	Space complexity
Worst case	O(n log n)	O(n)
Average case	O(n log n)	O(n)
Best case	O(n log n)	O(n)

Advantages:

• Guaranteed time complexity of O(n log n) in all cases (best, average, worst).
• Stable sort (maintains the relative order of equal elements).

Disadvantages:

• Requires additional memory O(n) for merging subarrays.