Python函数应用：如何实现归并排序算法

归并排序是一种使用递归的排序算法，它的基本思想是将一个待排序的序列划分为两个子序列，然后分别对两个子序列进行排序，最后将两个已经排好序的子序列合并成一个有序的序列。

实现归并排序的基本步骤如下：

1. 定义一个归并排序函数mergesort，该函数接受一个待排序的序列作为参数。

2. 如果序列的长度小于等于1，直接返回该序列，因为一个元素或者空序列都是有序的。

3. 将序列划分为两个子序列，分别调用mergesort函数对两个子序列进行排序。

4. 合并两个已经排好序的子序列，得到一个有序的序列。

5. 返回合并后的有序序列。

以下是一个用Python实现归并排序的例子：

# 定义归并排序函数
def mergesort(seq):
    # 如果序列长度小于等于1，直接返回序列
    if len(seq) <= 1:
        return seq
    
    # 将序列划分为两个子序列
    mid = len(seq) // 2
    left = mergesort(seq[:mid])
    right = mergesort(seq[mid:])
    
    # 合并两个已经排好序的子序列
    i = j = 0
    merged = []
    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
    merged += left[i:]
    merged += right[j:]
    
    # 返回合并后的有序序列
    return merged

# 测试归并排序函数
seq = [3, 2, 1, 5, 4]
sorted_seq = mergesort(seq)
print(sorted_seq)  # 输出 [1, 2, 3, 4, 5]

在这个例子中，我们定义了一个名为mergesort的函数，它接受一个待排序的序列seq作为参数。在函数内部，我们首先检查序列的长度，如果长度小于等于1，直接返回序列。否则，我们将序列划分为两个子序列left和right，分别调用mergesort函数对两个子序列进行排序。然后，我们定义了一个用于合并两个已经排好序的子序列的while循环，将较小的元素依次添加到merged列表中。最后，我们将剩余的元素添加到merged列表中，返回合并后的有序序列。

通过调用mergesort函数并传入一个待排序的序列，我们可以得到一个有序的序列。在上面的例子中，输入的序列为[3, 2, 1, 5, 4]，经过归并排序后，输出的序列为[1, 2, 3, 4, 5]。

归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。它是一种稳定的排序算法，适用于各种规模的数据集。在实际应用中，归并排序常用于外部排序和链表排序等场景。