Basic Idea of Merge Sort¶

Merge Sort is an efficient sorting algorithm based on the divide-and-conquer strategy. Its core idea can be summarized in three steps: Divide, Recursively Sort, and Merge.

• Divide: Split the array to be sorted into two halves from the middle until each subarray contains only one element (at this point, the subarray is already sorted).
• Recursively Sort: Recursively apply merge sort to the left and right subarrays until all subarrays are sorted.
• Merge: Combine two sorted subarrays into a larger sorted array, resulting in the final sorted array of the entire input.

In simple terms, merge sort breaks down a big problem into smaller ones, solves the small problems, and then combines the results.

Detailed Explanation of the Divide Process¶

Consider an array [3, 1, 4, 2]. The divide process of merge sort is as follows:

1. First Division: The array length is 4, and the middle position is 4//2 = 2. Thus, it is split into two halves: left = [3, 1] and right = [4, 2].
2. Recursive Division of Left Subarray [3, 1]: The middle position is 2//2 = 1, splitting into left_left = [3] and left_right = [1] (each subarray has length 1, so no further division is needed).
3. Recursive Division of Right Subarray [4, 2]: The middle position is 2//2 = 1, splitting into right_left = [4] and right_right = [2] (each subarray has length 1, so no further division is needed).

Recursive Sorting and Merging¶

When the subarrays are divided down to length 1, they are already sorted (a single element is inherently sorted). At this point, we perform the merge operation to combine two sorted subarrays into a larger sorted array.

Using the divided subarrays as examples:
- Merge Left Subarrays: [3] and [1] are merged into [1, 3].
- Merge Right Subarrays: [4] and [2] are merged into [2, 4].
- Final Merge: [1, 3] and [2, 4] are merged into [1, 2, 3, 4].

Python Code Implementation¶

The following is a Python implementation of merge sort, consisting of two parts: the merge function and the recursive sorting function:

1. Merge Function merge(left, right)¶

Function: Merges two sorted subarrays into a new sorted array.

def merge(left, right):
    merged = []  # Stores the merged result
    i = j = 0    # Pointers (indices) for the two subarrays

    # Compare elements from both subarrays and add them to merged in order
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # Add remaining elements from the unexhausted subarray
    merged.extend(left[i:])  # Add remaining elements in left
    merged.extend(right[j:]) # Add remaining elements in right
    return merged

2. Recursive Sorting Function merge_sort(arr)¶

Function: Recursively splits the array, calls merge to get the sorted result.

def merge_sort(arr):
    # Base case: array of length 1 or 0 is already sorted
    if len(arr) <= 1:
        return arr

    # Divide the array into two halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Recursively sort the left half
    right = merge_sort(arr[mid:])  # Recursively sort the right half

    # Merge the two sorted subarrays
    return merge(left, right)

Test Code¶

if __name__ == "__main__":
    test_array = [3, 1, 4, 2, 5]
    sorted_array = merge_sort(test_array)
    print("Original array:", test_array)
    print("Sorted array:  ", sorted_array)

Output:

Original array: [3, 1, 4, 2, 5]
Sorted array:  [1, 2, 3, 4, 5]

Characteristics of Merge Sort¶

• Time Complexity: Regardless of the input array, the time complexity of merge sort is always O(n log n) (total operations of divide and merge steps sum to O(n log n)).
• Space Complexity: Requires additional arrays to store merged results, so space complexity is O(n).
• Stability: Merge sort is a stable sorting algorithm (the relative order of equal elements is preserved).

The core of merge sort is “divide and conquer” and “merging sorted arrays.” By recursively dividing and merging, it achieves the sorting of the entire array. Although the code may seem more complex than simple sorts like bubble sort, it is intuitive and highly efficient once its underlying logic is understood.