sorting error in python

Question

def merge_lists(all_lst):
    def merge(left,right):
        results = []
        while left and right:
            if min(left) < min(right):
                results.append(min(left))
                left.remove(min(left))
            else:
                results.append(min(right))
                right.remove(min(right))
        results.extend(left)
        results.extend(right)
        return results
    if all_lst == []:
        return []
    elif len(all_lst) == 1:
        return merge(all_lst[0],[])
    else:
        return merge_lists([merge(all_lst[0],all_lst[1])] + all_lst[2:])

all_lst = [[2, 7, 10], [0, 4, 6], [3, 11],[123,88,7],[12,32,4,6,7],[34,22,1],[3]]
print(merge_lists(all_lst))
>>> [0, 1, 2, 3, 3, 4, 4, 6, 6, 7, 7, 7, 10, 11, 12, 22, 32, 34, 123, 88]

My code sorts the numbers in increasing order. But why is 88 not in the correct place? Is there anything wrong with my code?

Is this some kind of homework, where you can't use built-in functions ? Seems you are not the only one working on it stackoverflow.com/questions/22440361/… — Pierre
– Pierre, Commented Mar 17, 2014 at 13:26

tobias_k · Accepted Answer · 2014-03-17 14:21:39Z

4

The problem is in your merge function. Consider this input:

[0, 2, 3, 4, 6, 7, 10, 11] [123, 88, 7]

After some time, result is [0, 2, 3, 4, 6, 7, 7, 10, 11], left is [] and right is [123, 88] -- and now you exit the while loop and just extend result with all the rest of right, which is not sorted!

To fix this, you could sort both left and right, then you don't need to use min anymore, either, as the first element will then always be the smallest. Or, if you can't use builtin sort functions, continue picking the minimum element from left and right until both are exhausted.

edited Mar 17, 2014 at 14:21

answered Mar 17, 2014 at 13:17

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user1749431 · Accepted Answer · 2014-03-17 13:12:05Z

2

You need to sort the list with a sort function, Python sort() works

all_lst = [0, 1, 2, 3, 3, 4, 4, 6, 6, 7, 7, 7, 10, 11, 12, 22, 32, 34, 123, 88]

sorted_ls = sorted(all_lst)
print sorted_ls

output: [0, 1, 2, 3, 3, 4, 4, 6, 6, 7, 7, 7, 10, 11, 12, 22, 32, 34, 88, 123]

answered Mar 17, 2014 at 13:12

user1749431

5696 silver badges21 bronze badges

Comments

NPatel · Accepted Answer · 2014-03-17 13:13:24Z

0

please sort the list after adding all values.

all_lst.sort()

answered Mar 17, 2014 at 13:13

NPatel

21.4k17 gold badges104 silver badges165 bronze badges

Comments

BlackMamba · Accepted Answer · 2014-03-17 13:16:32Z

0

you should change your code to this

def merge(left,right):
    results = []
    left = sorted(left)
    right = sorted(right)
    while left and right:
        if min(left) < min(right):
            results.append(min(left))
            left.remove(min(left))
        else:
            results.append(min(right))
            right.remove(min(right))
    results.extend(left)
    results.extend(right)
    return results

when you do merge, you should keep left and right list are ordered.

answered Mar 17, 2014 at 13:16

BlackMamba

10.3k8 gold badges47 silver badges71 bronze badges

Collectives™ on Stack Overflow

sorting error in python

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related