0

For example, I have a list with many many elements

x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8], ...]

each element has already sorted.

How can I get a list named y that is from x's elements and sorted it?

3
  • What output do you want? please provide some output Commented Dec 7, 2016 at 7:28
  • Merge each pair of lists; repeat. (You can't get asymptotically better than that with comparison, or you could write merge sort that way.)
    – Ry-
    Commented Dec 7, 2016 at 7:29
  • en.wikipedia.org/wiki/Merge_algorithm#K-way_merging
    – Ry-
    Commented Dec 7, 2016 at 7:31

6 Answers 6

4

If I understand your question correctly, you should look into heapq.merge:

>>> import heapq
>>> lists = x = [[1, 2, 3], [3, 4, 5], [2, 3, 4], [4, 7, 8]]
>>> list(heapq.merge(*lists))
[1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 7, 8]
0
1

Here is a simple solution without any library:

x = [[1,2,3], [3,4,5], [2,3,4], [4,7,8]]

print(sorted([item for sublist in x for item in sublist]))

Returns: [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 7, 8]

0

If you just want to sort use sorted,try this

x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = sorted(x)
print y

If you want to get all elements in sorted way,try this

x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = sorted([item for sublist in x for item in sublist])
print y
0

You need a "merge" operation: just start with two lists and keep taking the element that is smaller; when one list is completed copy the eventually remaining elements from the other one...

def merge(A, B):
    result = []
    ia = ib = 0
    while ia < len(A) and ib < len(B):
        if a[ia] < b[ib]:
            result.append(A[ia])
            ia += 1
        else:
            result.append(B[ib])
            ib += 1
    # copy "tail"
    while ia < len(A):
        result.append(A[ia])
        ia += 1
    while ib < len(B):
        result.append(B[ib])
        ib += 1
    return result

If you have a collection of N lists just merge them in pairs and you will end up with half of them. Repeat until you get just one list.

6
  • I think that algorithmically, you can do better here... Specifically, consider the corner case where the list ranges don't overlap and the ranges are sorted in the way you want the -- [[1], [2], [3], ..., [100]]. Your algorithm which is to merge them 2 at a time will produce [1, 2] which needs to be merged with [3], then [4], then ... At each point, you need to look at all of the numbers that you've already merged before you can start putting in the new data. I think this leads to an O(N^2) merging time. If you know the mins from all of the lists, you can put them in a heap ...
    – mgilson
    Commented Dec 7, 2016 at 7:54
  • (continued) ... In other words, the best solution (I think) is to put all the mins in a single heap. pop/yield the global min. put the next item from the list who had the min onto the heap. repeat until all of the items have been put onto the heap and then just pop out the rest of the heap items. Unfortunately, this takes a good amount of book-keeping :-)
    – mgilson
    Commented Dec 7, 2016 at 7:58
  • Merging in pair means going from [[1], [2], [3], [4], [5], [6], ...] to [[1,2], [3,4], [5, 6], ...], not keeping merging the same list with all the other ones.
    – 6502
    Commented Dec 7, 2016 at 8:23
  • Right, but then don't you need to keep merging the merged pairs until you only have one list left? Isn't that what your last sentence says?
    – mgilson
    Commented Dec 7, 2016 at 14:22
  • @mgilson: yes, but every element will be processed only O(log(n)) times; complexity of merge sort (implemented correctly) is O(n*log(n)).
    – 6502
    Commented Dec 7, 2016 at 14:36
0

I am going to give you some pointers.

First, define a function merge(x, y) that gets two sorted lists and returns a combined sorted list.

Then, run merge on couples

[merge(lst[i], lst[i+1] ) for i in range(0,len(lst),2) ] 

This process should be repeated as long as the list has more than two elements, and if the number of elements is odd, append [] to it

0

Method 1:

import heapq
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = list(heapq.merge(*x))

Method 2:

import itertools
y = sorted(itertools.chain(*x))
2
  • You're better off using itertools.chain.from_iterable(x) (just to get in the habit)
    – mgilson
    Commented Dec 7, 2016 at 7:58
  • @ mgilson ths for the tip
    – 宏杰李
    Commented Dec 7, 2016 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.