给定一个无序序列a[10] = {4,3,1,2,6,5,0,9,8,7}，请用归并算法实现排序（分别采用传统的归并和链接表进行实现）。

归并排序是一种稳定的分治算法，可以将两个已排序的部分合并成一个有序的整体。对于给定的无序序列a[10]，我们可以按照以下步骤分别采用传统数组实现和链表实现归并排序：

### 1. 传统数组实现（两路归并）

**步骤**：
1. 将数组一分为二，直到每个子数组只有一个元素。
2. 合并相邻的子数组，将较小的元素放入结果数组，并不断向左移动指针直到其中一个子数组遍历完。
3. 将另一个子数组剩余部分复制到结果数组。
4. 重复步骤2、3，直到所有元素都被合并。

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

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

# 辅助函数：合并两个已经排好序的数组
def merge(left, right):
    merged = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # 把剩余部分加入结果
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    
    return merged

# 测试例子
arr = [4, 3, 1, 2, 6, 5, 0, 9, 8, 7]
sorted_arr = merge_sort(arr)

### 2. 链表实现（归并节点）

**步骤**：
1. 创建一个空链表作为临时存储。
2. 比较链表头的值，选择较小的一个添加到临时链表，并更新当前链表的头部。
3. 重复步骤2，直到其中一个链表为空。
4. 将另一个链表剩下的部分连接到临时链表的尾部。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_linked_lists(head1, head2):
    dummy = ListNode(0)
    current = dummy

    while head1 and head2:
        if head1.val <= head2.val:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next

    if head1:
        current.next = head1
    elif head2:
        current.next = head2

    return dummy.next

# 对数组转换为链表（假设数组列表是arr）
arr_to_link = [ListNode(val) for val in arr]
head = arr_to_link[0]
for i in range(1, len(arr)):
    arr_to_link[i].next = arr_to_link[i+1]
head = merge_linked_lists(head, None)  # 初始化第二个链表为空

# 然后再次对链表进行排序
sorted_list = merge_linked_lists(head, None)