Sorting by checking 2 distance away elements in a list, and check the method's accuracy

Question

This code works as follows : It accepts number of test case T. For each test case, it accepts length of sequence of integers N and the sequence (or list) itself L.

The goal is to sort the list by checking every three consecutive elements, but only comparing the ends. L[i] and L[i+2]. If the right side is less than left one, then these two have to be swapped. This algorithm will continue until nothing can be swapped.

The problem is, my code works for N < 100. Also work for N larger but very slow, exceeded the time limit which is 20 secs.

If the list ended up sorted correctly, the output must be 'OK'.

If the list ended up not sorted, the output must be the first index in which the next index has element less than it.

This is part of google code jam 2018 qualificatiom round, finished already.

How to optimize this in Python..? What are the arguments? Thanks.

    T = input()

    N = []
    L = []
    output = []

    for t in range(T):

        N.append(input())
        L.append(raw_input())


    def trouble(l, n):
        repeat = True
        while repeat:

            repeat = False 
            for index in range(0,n-2):
                if l[index] > l[index+2]:
                    repeat = True
                    dum = l[index:index+3]
                    l[index] = dum[-1]
                    l[index+2] = dum[0]
                    del dum
        return l

    def search(l, n):

        for i in range(n):

            if l[i] > l[i+1]:

                return i

    for i in range(T):

        l = L[i].split()
        l = [int(num) for num in l]
        res = trouble(l, N[i])
        if res == sorted(l):
            output.append('OK')
        else:
            output.append(search(l, N[i]))

    for t in range(T):

        print('Case #'+str(t+1)+': '+str(output[t]))

Answer 1

With python 2.7, you have xrange. The improvement in performance might be minimal (but an improvement nonetheless):

The advantage of xrange() over range() is minimal (since xrange() still has to create the values when asked for them) except when a very large range is used on a memory-starved machine or when all of the range’s elements are never used (such as when the loop is usually terminated with break).

---

Split your \$ L \$ and use map as soon as possible.

L.append(map(int, raw_input().split()))

---

Swapping in python is as easy as:

a, b = b, a

No need to allocate a temporary dummy (and del it later):

if l[index] > l[index + 2]:
    repeat = True
    l[index], l[index + 2] = l[index + 2], l[index]

---

Now, for the time limit issue, since you know that you are actually sorting the even and odd indexes sublists disjointly; splice your \$ L \$ and sort those. Then, reattach them both by weaving them together.

# L has been read from user
l_even = sorted(l[::2])
l_odd = sorted(l[1::2])

and then join them together.