数据结构编制一个能演示将两个有序表合并为一个有序表的程序

数据结构中的排序算法经常涉及合并两个已排序的列表创建一个新的有序列表。这里以归并排序为例，它通常包含一个递归过程，可以展示这个过程。下面是一个简单的Python代码示例：

def merge_sorted_lists(list1, list2):
    # 创建一个空的结果列表
    merged_list = []
    
    # 使用两个指针分别指向两个输入列表的起始位置
    i = 0
    j = 0
    
    # 当两个列表都有剩余元素时，比较当前元素并添加较小的一个到结果列表
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            merged_list.append(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1
    
    # 如果其中一个列表已经遍历完，直接将另一个列表剩余部分追加到结果
    merged_list.extend(list1[i:])
    merged_list.extend(list2[j:])
    
    return merged_list

# 示例
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged_list = merge_sorted_lists(list1, list2)
print("Merged sorted list:", merged_list)