Comparison issue during Python Implementation of Queue & Deque Sort

I am trying to implement some sort of "Queue" where I want to try to sort the elements of a Queue. The point here is to see whether a specific queue can be sorted using queue and deque operations.

I do this by comparing the first and last elements of the queue, then appending the bigger one to a new list, removing this item from the queue. In the end I am supposed to have a new list, sorted as long as queue-deque operations let.

However in a specific test case, my algorithm carries out the comparison of two elements in my queue wrong.

# the queue I am trying to "sort" is:
lst = "1000000842 1000000721 1000000671 1000000663 1000000626 1000000520 1000000126 999999978 1000000266 1000000501".split(" ")
# the new list that I will add my numbers from the start and the end of my queue.
new_lst = []

for x in range(len(lst)-1):
    if lst[0] >= lst[-1]:
        new_lst.append(lst[0])
        del lst[0]
    if lst[0] < lst[-1]:
        new_lst.append(lst[-1])
        del lst[-1]
    print(new_lst)

This code produces the new_list as:

['1000000842', '1000000721', '1000000671', '1000000663', '1000000626', '1000000520', '1000000501', '1000000266', '999999978', '1000000126']

where it should have been:

['1000000842', '1000000721', '1000000671', '1000000663', '1000000626', '1000000520', '1000000501', '1000000266', '1000000126', '999999978']

I figured the issue occurs in "1000000126 999999978 1000000266" part. It compares "999999978" and "1000000126" and adds "999999978" to the new list rather than "1000000126". Why? I could not figure it out yet.

Solution

You have struck an issue with Python that is quite common and can be very confusing at times; namely type conversion!

When you are splitting your list (or queue) I believe perhaps you meant convert each items's type to integer:

list(map(int, "1000000842 1000000721 1000000671 1000000663 1000000626 1000000520 1000000126 999999978 1000000266 1000000501".split(" ")))

Otherwise you are essentially comparing two strings to check which one is bigger/smaller.

In your case in the 2nd last iteration:

>>> "1000000126" >= "999999978"
False
>>>

So the items are never swapped since your expression evaluates to False. Now if you convert your list items to integer you should see

>>> 1000000126 >= 999999978
True