排序已按升序排序的n个固定段的列表

Question

问题如下：

由一个固定数量的n个端到端连接的段组成的列表，每个段已经按升序排列。

我考虑过使用mergesort，基本情况是，如果等于n，那么返回并合并它们，因为我们已经知道它们是排序的，但是如果我有3个段，它将不起作用，因为我除以2，你不能将3个段平均分成两部分。

另一种方法类似于合并排序。所以我对每个段使用n个堆栈，如果L[i]，我们可以识别它

如果你有主意的话，伪代码会很好。

编辑：

一个例子是[（14,20,22），（7,8,9），（1,2,3）]，这里我们有3段3个元素，即使这些段被排序了，整个列表也没有。

p. s.（）仅用于指出段

Answer 1

我想你可能误解了我的意思。通常情况下，在合并之前，你会把每一半分成两半，并对每一半进行排序，但实际上是合并部分构成了算法。您只需在运行时合并即可。

使用[（14,20,22),(7,8,9),(1,2,3)]的示例

第一次合并后，您有[（7, 8, 9, 14, 20, 22),(1, 2, 3)]

第二次合并后，您有[（1、2、3、7、8、9、14、20、22）]

l = [14, 20, 22, 7, 8, 9, 1, 2, 3]

rl = [] # run list
sl = [l[0]] # temporary sublist

#split list into list of sorted sublists
for item in l[1:]:
    if item > sl[-1]:
        sl.append(item)
    else:
        rl.append(sl)
        sl = [item]
rl.append(sl)
print(rl)

#function for merging two sorted lists
def merge(l1, l2):
    l = [] #list we add into
    while True:
        if not l1:
            # first list is empty, add second list onto new list
            return l + l2
        if not l2:
            # second list is empty, add first list onto new list 
            return l + l1
        if l1[0] < l2[0]:
            # rather than deleting, you could increment an index
            # which is likely to be faster, or reverse the list
            # and pop off the end, or use a data structure which
            # allows you to pop off the front
            l.append(l1[0])
            del l1[0]
        else:
            l.append(l2[0])
            del l2[0]

# keep mergins sublists until only one remains
while len(rl) > 1:
    rl.append(merge(rl.pop(), rl.pop()))

print(rl)

值得注意的是，除非这只是一个练习，否则你最好使用你选择的语言使用的任何内置排序函数。