Python归并排序如何实现？-杰瑞科技汇

Of course! Here is a detailed explanation and implementation of the Merge Sort algorithm in Python, including a step-by-step breakdown, code, and analysis.

（图片来源网络，侵删）

What is Merge Sort?

Merge Sort is a highly efficient, stable, and comparison-based sorting algorithm. It follows the Divide and Conquer paradigm, which means it breaks a problem down into smaller, more manageable sub-problems, solves them recursively, and then combines their solutions to solve the original problem.

The core idea of Merge Sort is to:

Divide: Recursively split the input array into two halves until each sub-array contains only one element. An array with one element is, by definition, already sorted.
Conquer (Merge): Merge the sorted sub-arrays back together in a way that produces a single, sorted array. This is the key step.

Step-by-Step Example

Let's sort the array: [38, 27, 43, 3, 9, 82, 10]

Step 1: Divide Phase (Recursive Splitting)

The algorithm keeps splitting the array in half until it can't be split anymore (i.e., until the sub-arrays have a size of 1).

（图片来源网络，侵删）

[38, 27, 43, 3, 9, 82, 10]
       /           \
[38, 27, 43, 3]    [9, 82, 10]
    /      \        /      \
[38, 27]   [43, 3]  [9, 82]  [10]
  /  \       /  \     /  \     |
[38] [27]   [43] [3] [9] [82]  [10]

At this point, we have a list of single-element arrays, which are all considered sorted.

Step 2: Conquer Phase (Merging)

Now, we merge these small sorted arrays back together, ensuring the merged result is also sorted.

Merge [38] and [27]:
- Compare 38 and 27. 27 is smaller.
- Result: [27, 38]
Merge [43] and [3]:
（图片来源网络，侵删）
- Compare 43 and 3. 3 is smaller.
- Result: [3, 43]
Merge [9] and [82]:
- Compare 9 and 82. 9 is smaller.
- Result: [9, 82]
Current state of merges:
```
[27, 38]   [3, 43]   [9, 82]   [10]
```
Merge [27, 38] and [3, 43]:
- Compare the first elements: 27 vs 3. 3 is smaller. Add 3 to the result.
- Compare 27 vs 43. 27 is smaller. Add 27 to the result.
- Compare 38 vs 43. 38 is smaller. Add 38 to the result.
- The [3, 43] array is now empty. Add the rest of [27, 38], which is just 38.
- Result: [3, 27, 38, 43]
Merge [9, 82] and [10]:
- Compare 9 vs 10. 9 is smaller. Add 9 to the result.
- Compare 82 vs 10. 10 is smaller. Add 10 to the result.
- The [10] array is now empty. Add the rest of [9, 82], which is 82.
- Result: [9, 10, 82]
Current state of merges:
```
[3, 27, 38, 43]   [9, 10, 82]
```
Final Merge: [3, 27, 38, 43] and [9, 10, 82]:
- Compare 3 vs 9. 3 is smaller. Add 3.
- Compare 27 vs 9. 9 is smaller. Add 9.
- Compare 27 vs 10. 10 is smaller. Add 10.
- Compare 27 vs 82. 27 is smaller. Add 27.
- Compare 38 vs 82. 38 is smaller. Add 38.
- Compare 43 vs 82. 43 is smaller. Add 43.
- The first array is now empty. Add the rest of the second array, which is 82.
- Final Sorted Result: [3, 9, 10, 27, 38, 43, 82]

Python Implementation

We'll implement this using two functions:

merge_sort(arr): The main recursive function that handles the "Divide" step.
merge(left, right): A helper function that handles the "Conquer" (merging) step.

def merge_sort(arr):
    """
    Sorts an array in ascending order using the Merge Sort algorithm.
    Args:
        arr (list): The list of elements to be sorted.
    Returns:
        list: A new list containing the sorted elements.
    """
    # Base case: If the array has 0 or 1 element, it's already sorted.
    if len(arr) <= 1:
        return arr
    # Divide Step: Find the middle of the array.
    mid = len(arr) // 2
    # Recursively sort the left half.
    left_half = merge_sort(arr[:mid])
    # Recursively sort the right half.
    right_half = merge_sort(arr[mid:])
    # Conquer Step: Merge the sorted halves.
    return merge(left_half, right_half)
def merge(left, right):
    """
    Merges two sorted lists into a single sorted list.
    Args:
        left (list): A sorted list.
        right (list): A sorted list.
    Returns:
        list: A new list containing all elements from left and right in sorted order.
    """
    merged_list = []
    left_index = 0
    right_index = 0
    # Traverse both lists and compare elements at the current index.
    # Append the smaller element to the merged_list and move that list's index forward.
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged_list.append(left[left_index])
            left_index += 1
        else:
            merged_list.append(right[right_index])
            right_index += 1
    # After the main loop, one of the lists might still have elements.
    # Append the remaining elements from the non-empty list to the merged_list.
    # This works because the remaining elements are already sorted.
    if left_index < len(left):
        merged_list.extend(left[left_index:])
    elif right_index < len(right):
        merged_list.extend(right[right_index:])
    return merged_list
# --- Example Usage ---
my_array = [38, 27, 43, 3, 9, 82, 10]
print(f"Original array: {my_array}")
sorted_array = merge_sort(my_array)
print(f"Sorted array:   {sorted_array}")
# Another example
another_array = [5, 1, 4, 2, 8, 0, 2]
print(f"\nOriginal array: {another_array}")
sorted_another_array = merge_sort(another_array)
print(f"Sorted array:   {sorted_another_array}")

In-Place Merge Sort (Advanced)

The standard implementation above is not "in-place," meaning it creates new lists during the merge process, using extra memory (O(n) space complexity). A more advanced, in-place version exists but is significantly more complex to implement correctly. The version above is the most common and easiest to understand.

Complexity Analysis

Time Complexity: O(n log n)
- Divide Step: The array is split in half log n times. This is because you are repeatedly dividing the problem size by 2.
- Conquer Step (Merge): The merge function takes O(n) time because it needs to look at every element in the two sub-arrays once to merge them.
- Total: log n splits * n work per merge = O(n log n).
- This time complexity is consistent for all cases: Best, Average, and Worst. This makes it very reliable.
Space Complexity: O(n)
- Merge Sort is not an in-place algorithm. During the merge step, it requires a temporary array (the merged_list in our code) to store the merged result.
- The maximum size of this temporary array will be n (when merging the two largest halves).
- Additionally, the recursive calls use O(log n) stack space, but the dominant factor is the O(n) temporary storage.

Advantages and Disadvantages

Advantages

Guaranteed O(n log n) Performance: Its performance is consistent and not affected by the initial order of the data.
Stable: Merge Sort is a stable sorting algorithm. This means that if two elements have equal values, their relative order in the original array will be preserved in the sorted array. (This is because we use <= in the merge function).
Well-suited for Linked Lists: It works very efficiently on linked lists because merging doesn't require extra space for elements to be shifted around.

Disadvantages

Not In-Place: It requires O(n) extra space, which can be a significant drawback for very large datasets.
Slower for Small Datasets: For small arrays, the overhead of recursion and creating new lists can make it slower than simpler algorithms like Insertion Sort or Bubble Sort. This is why hybrid algorithms (like Timsort, used in Python) use Merge Sort for large chunks and switch to a simpler algorithm for small ones.

Python归并排序如何实现？

What is Merge Sort?

Step-by-Step Example