实现Python中的归并排序算法的函数

归并排序（Merge sort）是一种分治排序算法，采用递归的方式将数组分成两个子数组，将两个子数组排序，然后将两个已排序的子数组合并成一个有序的数组。归并排序是稳定的排序算法，其时间复杂度为O(nlogn)。

以下是Python中实现归并排序算法的函数：

def mergeSort(arr):
    if len(arr) > 1:
        # Divide the array into two halves
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        # Recursively sort the two halves
        mergeSort(left)
        mergeSort(right)
        
        # Merge the sorted halves
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        # Copy any remaining elements of left or right
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

在上述函数中，首先判断传入数组是否可以继续拆分（长度大于1），若可以，就将数组分成两个子数组，递归调用归并排序函数对两个子数组进行排序。在排序完两个子数组之后，将它们合并成一个有序数组。在合并两个子数组时，我们使用三个指针i、j、k来遍历左子数组、右子数组和合并后的数组，依次比较左子数组元素和右子数组元素的大小，将较小的元素放入合并后的数组中，并移动指针。最后，将剩余的左子数组或右子数组中的元素复制到合并后的数组中即可。

下面是一个实例，演示如何使用上述函数对一个数组进行归并排序：

# Example usage of the mergeSort function:
arr = [9, 2, 6, 5, 4, 8, 1, 3, 7]
mergeSort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

上述代码首先定义一个待排序的数组，然后调用mergeSort函数对该数组进行排序。最后，输出排序后的数组。

总结：

归并排序是一种高效的排序算法，其时间复杂度为O(nlogn)，稳定性也很好。在Python中实现归并排序算法的函数，只需要递归调用函数实现拆分和排序，再合并两个有序子数组即可。无论是对大规模的数据还是小规模的数据，归并排序都表现出较好的性能。