举例线性对数时间复杂度的代码

一个常见的线性对数时间复杂度的例子是归并排序（Merge Sort）算法。以下是使用Python实现的归并排序代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分治法，将数组分为左右两半
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[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

这个算法的时间复杂度是O(n log n)，其中n是待排序数组的长度。该算法使用了分治法的思想，将数组分为两半，分别对左右两半进行排序，然后将它们合并起来。在合并的过程中，需要对左右两个数组进行比较，时间复杂度为O(n)，而在分治的过程中，每次将数组对半分，时间复杂度为O(log n)。因此，整个算法的时间复杂度为O(n log n)。