Python归并排序实现中使用append()是否存在性能隐患？

Great question—let’s unpack this step by step, since it touches on both Python’s list internals and trade-offs in algorithm implementation. First, let’s recap the two implementations you’re comparing:

Your merge sort implementation (using append()) #

def merge(l, r, direction):
    # print('merging')
    # print(l, r)
    # adding infinity to end of list so we know when we've hit the bottom of one pile
    l.append(inf)
    r.append(inf)
    A = []
    i, j = 0, 0
    while (i < len(l)) and (j < len(r)):
        if l[i] <= r[j]:
            A.append(l[i])
            i += 1
        else:
            A.append(r[j])
            j += 1
    # removing infinity from end of list
    A.pop()
    return(A)

def merge_sort(num_lst, direction='increasing', level=0):
    if len(num_lst) > 1:
        mid = len(num_lst)//2
        l = num_lst[:mid]
        r = num_lst[mid:]
        l = merge_sort(l, level=level + 1)
        r = merge_sort(r, level=level + 1)
        num_lst = merge(l, r, direction)
    return num_lst

In-place merge example (using index overwriting) #

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L[i] = arr[l + i]
    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
    while i < n1 and j < n2 :
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

Core Questions Answered #

1. Is using append() a "bad" implementation choice? #

Short answer: No. It’s a perfectly valid approach with clear trade-offs, but it’s not inherently worse than the in-place index method. Here’s why:

List resizing overhead is manageable

You’re correct that Python lists are dynamic arrays—when they exceed their pre-allocated capacity, they copy elements to a larger memory block. However, this overhead is amortized O(1) for append(): Python pre-allocates extra space (typically ~1.5x the current size) when resizing, so most append() operations are fast. The occasional expensive resize is spread out across many operations, making the average cost negligible for all but the most extreme datasets.

append() vs. index access: The performance gap is tiny

Index access (e.g., arr[k] = value) is a direct memory write, which is very fast. append() does have a tiny bit of extra overhead: it checks if the list has space, and if not, triggers a resize. But this check is a simple comparison, and resizes happen rarely. In practice, Python’s optimized C-level implementation makes both operations extremely fast—you’d struggle to measure a meaningful difference in most real-world scenarios.

2. Trade-offs between the two approaches #

Let’s break down the pros and cons of each method:

• Your append() approach:

  • ✅ Readability: The code is clean, straightforward, and avoids the complexity of tracking multiple indices for the original array.
  • ✅ Safety: You’re not modifying the input list, which avoids unintended side effects.
  • ❌ Memory overhead: You create a new list for each merge, which means you’re using extra memory temporarily (though both approaches still have an overall O(n) space complexity for merge sort, since the in-place example also creates temporary arrays L and R).

• In-place index approach:

  • ✅ Memory efficiency: Reuses the input array’s memory instead of creating new lists, which can help in memory-constrained environments.
  • ❌ Complexity: Requires tracking three separate indices (i, j, k) and handling subarray ranges, which makes the code harder to read and easier to mess up.

A small optimization note for your code #

Adding inf to the end of l and r is a clever way to simplify the merge loop, but it’s limited to numeric data. For a more general-purpose implementation, you could handle remaining elements explicitly after the main loop (like the in-place example does), which works for any comparable data type. That said, your trick is totally valid for numeric lists!

Final Takeaway #

Your implementation is completely correct and has the huge advantage of being easy to read and maintain. For most standard-sized datasets, the append() approach will perform just fine. If you’re working with extremely large data or need to optimize for absolute memory usage, the in-place index method might be worth considering—but at the cost of code complexity.

At the end of the day, merge sort’s core strength is its consistent O(n log n) time complexity, and both implementations preserve that. Choose the approach that best fits your readability needs and performance constraints.

内容的提问来源于stack exchange，提问作者RhythmInk