如何高效地将n维列表排序为一个列表

Question

input [[1,4,5],[1,3,4],[2,6]]

output [1,1,2,3,4,4,5,6]

我已经做了一个婴儿的方式，把每个值放在一个进程列表中，它需要2个循环 和另一个用于排序的循环

有没有办法在O（n）范围内或尽可能快地完成，或者不使用任何函数

def sortmerge(inputList):
    processList = []
    sortedList= []
    for i in range(len(inputList)):
        for j in range(len(inputList[i])):
            processList.append(inputList[i][j])
    # processList.sort()
    while processList:
        minimum = processList[0] 
        for x in processList: 
            if x < minimum:
                minimum = x
        sortedList.append(minimum)
        processList.remove(minimum)
    return sortedList

Answer 1

根据your comment，子列表可能无法排序。因此，O（n）是不可能的，因为需要排序，但是您可以通过展平然后排序来获得O（n log n）

from itertools import chain

inputList = [[1, 4, 5], [1, 3, 4], [2, 6]]
print(sorted(chain.from_iterable(inputList)))  # -> [1, 1, 2, 3, 4, 4, 5, 6]

（^{}使用TimSort，这是O（nlogn），链接是O（n））

如果您能对输入数据做出更多保证，可能会有比这更快的方法。例如，如果只有少数子列表可能未排序，则排序它们然后合并可能会更快

_{由于deceze将此解决方案发布到comment}