Code for finding close to optimal sorting networks

The code listed below finds sorting networks as described here:
http://en.wikipedia.org/wiki/Sorting_network

The sorting network it found for 12 items is close to what's been proven optimal, it took 43 steps instead of the proven optimal betweeen 37 and 39...
[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11], [0, 2], [1, 3], [1, 2], [4, 6], [5, 7], [5, 6], [8, 10],[9, 11], [9, 10], [0, 4], [1, 5], [2, 6], [3, 7], [1, 4], [2, 4], [3, 5], [3, 4], [5, 6],   [0, 8], [1, 9], [2, 10], [3, 11], [1, 8], [2, 8], [3, 9], [4, 10], [5, 11], [3, 8], [4, 8], [5, 9], [6, 10], [7, 11], [5, 8], [6, 8], [7, 9], [7, 8], [9, 10]]

A slight modification of the code found one with one more step (44) but one less depth, for a depth of 9:
[[10, 11], [8, 9], [6, 7], [4, 5], [2, 3], [0, 1], [9, 11], [8, 10], [9, 10], [5, 7], [4, 6], [5, 6], [1, 3], [0, 2], [1, 2], [7, 11], [6, 10], [5, 9], [4, 8], [7, 10], [7, 9], [6, 8], [7, 8], [5, 6], [3, 11], [2, 10], [1, 9], [0, 8], [3, 10], [3, 9], [2, 8], [1, 7], [0, 6], [3, 8], [3, 7], [2, 6], [1, 5], [0, 4], [3, 6], [3, 5],   [2, 4], [3, 4], [1, 2], [10, 11]]

I found that one with 64 comparators and depth of 10 could be found by "seeding" the process with these starting values that I had kind of seen the pattern of in the above results:
Seed Values: [[15, 14], [13, 12], [11, 10], [9, 8], [7, 6], [5, 4], [3, 2], [1, 0], [15, 13], [14, 12], [11, 9], [10, 8], [7, 5], [6, 4], [3, 1], [2, 0]]
And the whole network:
[[15, 14], [13, 12], [11, 10], [9, 8], [7, 6], [5, 4], [3, 2], [1, 0], [15, 13], [14, 12], [11, 9], [10, 8], [7, 5], [6, 4], [3, 1], [2, 0], [13, 14], [9, 10], [5, 6], [1, 2], [11, 15], [9, 13], [10, 14], [8, 12], [10, 15], [8, 13], [13, 14], [9, 10], [8, 15], [3, 7], [1, 5], [2, 6], [0, 4], [2, 7], [0, 5], [5, 6], [1, 2], [0, 7], [7, 15], [5, 13], [6, 14], [4, 12], [0, 8], [2, 10], [1, 9], [3, 11], [7, 11], [5, 9], [6, 10], [4, 8], [10, 15], [8, 13], [4, 9], [6, 11], [0, 5], [2, 7], [13, 14], [9, 10], [8, 15], [5, 6], [4, 11], [1, 2], [0, 7], [14, 15]]

The concept is that you start with a list A of every unique string of a certain length pf 0's and 1's and you provisionally try every possible pairwise swap on that list and find the swap that after that swap is done on every element of A (making a list B of strings of 1's and 0's) has the greatest intersection of A and B, meaning the most strings are the same between the two. The union becomes the new A and iterated. The greatest intersection also means it has the smallest union, so the idea is that this union will generally be smaller than A. I found that there is a non-zero intersection (And smaller union!) all the way until you end up with L lists of length L each one a sorted version of the L possible initial weights (where each 1 in the initial string is adding one to the weight). This means every possible list has been mapped to one of those lists via the swapping and thus all the lists can be sorted with those swaps. By the One-Zero principle it means every list of L sortable items can be sorted just as well with those swaps...

I know this isn't explained well in words but the code is fairly simple and works fairly quickly even written in single threaded python finding the network above only took a couple of minutes...

***Source Code***
import random
def copy(a):
    a1 = []
    for e in a:
        a1.append(e)
    return a1

def cullswap(s, sw):
    t = []
    for n in range(0, len(s)):
        a = copy(s[n])
        if s[n][sw[0]] > s[n][sw[1]]:
            swap(a, sw[0], sw[1])
            if finddupe(a, n, s) == False:
                t.append(a)
        else:
            t.append(s[n])
    return t
def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
def finddupe(a, n, s):
    for e in range(0, len(s)):
        if s[e] == a and e != n:
            return True
    return False
def bestswap(s):
    best = 0
    bestij = []
    for i in range(0, len(s[0])-1):
        for j in range(i+1, len(s[0])):
            count = 0
            for n in range(0, len(s)):
                if s[n][i] > s[n][j]:
                    a = copy(s[n])
                    swap(a, i, j)
                    if finddupe(a, n, s) == True:
                        count +=1
            if count > best:
                best = count
                bestij = [i,j]
    return bestij, best
def addelement(s,a, listlength):
    if len(a) < listlength:
        a1 = copy(a)
        a1.append(0)
        addelement(s, a1, listlength)
        a2 = copy(a)
        a2.append(1)
        addelement(s, a2, listlength)
    else:
        s.append(a)
def main():
    listlength = 12
    s = []
    addelement(s, [], listlength)
    swaps = []
    i = 0
    while(len(s) > 0):
        swap, best = bestswap(s)
        i+=1
        print(i, swap)
        swaps.append(swap)
        if best == 0:
            break
        s = cullswap(s, swap)
    print(swaps, len(swaps))  


main()

** Slower, but Depth optimizing source code**
import random
def copy(a):
    a1 = []
    for e in a:
        a1.append(e)
    return a1

def cullswap(s, sw):
    t = []
    for n in range(0, len(s)):
        a = copy(s[n])
        if s[n][sw[0]] > s[n][sw[1]]:
            swap(a, sw[0], sw[1])
            if finddupe(a, n, s) == False:
                t.append(a)
        else:
            t.append(s[n])
    return t
def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
def finddupe(a, n, s):
    for e in range(0, len(s)):
        if s[e] == a and e != n:
            return True
    return False
def finddepth(swaps, newswap):
    
    for k in range(len(swaps)-1, 0, -1):
        if swaps[k][0] == newswap[0] or swaps[k][0] == newswap[1] or swaps[k][1] == newswap[0] or swaps[k][1] == newswap[1]:
            return len(swaps)-k
    return len(swaps)
def bestswap(s, swaps):
    best = 0
    bestij = []
    for i in range(0, len(s[0])-1):
        for j in range(i+1, len(s[0])):
            count = 0
            d = -1
            for n in range(0, len(s)):
                if s[n][i] > s[n][j]:
                    a = copy(s[n])
                    swap(a, i, j)
                    if finddupe(a, n, s) == True:
                        count +=1
            if count >= best:
                f = finddepth(swaps, [i,j])
                if f > d:
                    d = f
                    best = count
                    bestij = [i,j]
    return bestij, best
def addelement(s,a, listlength):
    if len(a) < listlength:
        a1 = copy(a)
        a1.append(0)
        addelement(s, a1, listlength)
        a2 = copy(a)
        a2.append(1)
        addelement(s, a2, listlength)
    else:
        s.append(a)
def main():
    listlength = 14
    s = []
    addelement(s, [], listlength)
    swaps = []
    i = 0
    while(len(s) > 0):
        swap, best = bestswap(s, swaps)
        i+=1
        print(i, swap)
        swaps.append(swap)
        if best == 0:
            break
        s = cullswap(s, swap)
    print(swaps, len(swaps))  

main()


**Code for starting with a certain "seeding" network**
import random
def copy(a):
    a1 = []
    for e in a:
        a1.append(e)
    return a1

def cullswap(s, sw):
    t = []
    for n in range(0, len(s)):
        a = copy(s[n])
        if s[n][sw[0]] > s[n][sw[1]]:
            swap(a, sw[0], sw[1])
            if finddupe(a, n, s) == False:
                t.append(a)
        else:
            t.append(s[n])
    return t
def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
def finddupe(a, n, s):
    for e in range(0, len(s)):
        if s[e] == a and e != n:
            return True
    return False
def finddepth(swaps, newswap):
    
    for k in range(len(swaps)-1, 0, -1):
        if swaps[k][0] == newswap[0] or swaps[k][0] == newswap[1] or swaps[k][1] == newswap[0] or swaps[k][1] == newswap[1]:
            return len(swaps)-k
    return len(swaps)
def bestswap(s, swaps, starter):
    best = 0
    bestij = []
    if len(swaps) < len(starter):
        return starter[len(swaps)], 1
    for i in range(0, len(s[0])-1):
        for j in range(i+1, len(s[0])):
            count = 0
            d = -1
            for n in range(0, len(s)):
                if s[n][i] > s[n][j]:
                    a = copy(s[n])
                    swap(a, i, j)
                    if finddupe(a, n, s) == True:
                        count +=1
            if count >= best:
                f = finddepth(swaps, [i,j])
                if f > d:
                    d = f
                    best = count
                    bestij = [i,j]
    return bestij, best
def addelement(s,a, listlength):
    if len(a) < listlength:
        a1 = copy(a)
        a1.append(0)
        addelement(s, a1, listlength)
        a2 = copy(a)
        a2.append(1)
        addelement(s, a2, listlength)
    else:
        s.append(a)
def main():
    listlength = 16
    s = []
    addelement(s, [], listlength)
    starter = [[15,14],[13,12],[11,10],[9,8],[7,6],[5,4],[3,2],[1,0], [15,13],[11,9],[7,5],[3,1],[4,0], [5,1],[6,2],[7,3],[8,12],[9,13],[10,14],[11,15]]
    swaps = []
    i = 0
    while(len(s) > 0):
        swap, best = bestswap(s, swaps, starter)
        i+=1
        print(i, swap)
        swaps.append(swap)
        if best == 0:
            break
        s = cullswap(s, swap)
    print(swaps, len(swaps))  

main()

Prime sort

My idea was considering you have a list L of N items, and a list of primes P1...Q including 1, listed in reverse order like so:

Here Q is 89...
[89,83, 79, 73, 71, 67, 63, 61, 59, 53, 47, 43, 41, 37, 31, 29,23,19, 17,13, 11, 7, 5, 3, 2, 1]

My algorithm first compares every number up to N-P1 in L at position i to the number at position i+P1 , so in the example above it would compare the first item in the list at i=0 to the 89th, the i=1 number to 90, up to N-89 and N.

This is then done for every P on the list, and I found that with Q = 89 this could sort all of the random lists I tried of 1000 items,

Q varies somehow with N, I found that

N        Q
32       13
100     23
1000   89

It seems to me that the relationship might be that the number of primes in the list P should be around the square root of N...

The single threaded source code listed below is very simple, but it's actually possible to make a concurrent version where the prime P(j) loop starts as soon as the i counter for the P(j-1) loop is P(j-1)+1 through the list... So potentially many "waves" of comparisons could be going through the list simultaneously...

**For tournaments**

I think it might be good for a tournament at some game, but one where the total number of matches played for a person is minimized over the need to play concurrent matches, and where the most important thing is to make as many good matches as possible. Because each round everyone has a chance to climb up the ladder as far as they can go, and the people they're playing would generally be getting closer and closer to the same skill level as the rounds progressed making for better and better matches, Some concurrency is possible as the jth round of matches can start as soon as the prior round's i counter is P(j-1) up the list, and so on until many rounds are travelling like waves through the list... Mathematically there is the potential for someone to work their way up the ladder 1 step at a time from the bottom to the top, but statistically that's improbable as they wouldn't be that far down the ladder by the last round if they were good enough to win so many consecutive matches against increasingly tough opponents. The nature of this algorithm is that losing wouldn't punish anyone too much; they could still end up winning the whole tournament overall no matter where they are in the randomized list in the final round though it's easier to climb early on...And losing later and later on matters less and less to the person's final ranking... Adding a couple rounds over what's strictly necessary for the ideal case of numbers accentuates the fairness of the final ranking...
Source Code:
import random
def swap(l, i, ip):
    if l[i] > l[ip]:
        temp = l[ip]
        l[ip] = l[i]
        l[i] = temp        
def main():
    l = []
    for i in range(0, 1000):
        l.append(i)
    random.shuffle(l)
    p = [89,83, 79, 73, 71, 67, 63, 61, 59, 53, 47, 43, 41, 37, 31, 29,23,19, 17,13, 11, 7, 5, 3, 2, 1]
    print(l)
    for prime in p:
        for i in range(0, 1000-prime):
            swap(l, i, i+prime)
    print(l)
main()

+- 40% curve

I found a curve that smoothly piece-wise interpolates a set of  a waves values along the integers and proved something interesting about it...

Given final and initial y values for each interval between integers, the curve smoothly connects those points such that the integral of the curve over the interval is either very close to 40% greater than the integral of the function that is a straight line connecting the two points or very close to 40% less, depending on whether it is concave up or down and which side of the x axis the curve is on... The two formulas for concavity work as follows: The concavity will be up if the Final point is greater than or equal to the Initial point, in which case the other formula will be concave down, and vice versa... I've chosen the above example to have alternating concavities using alternating formulas, it doesn't work for always increasing or always decreasing functions...
**Proofs**
The integral of the curve written above is very nearly .6 times the sum of the endpoints over the interval from -1..1 which is about 60% what the integral would be for a straight line connecting the two points by the average value formula...

Note the integral of the average value over the interval is multiplied by 2, or F+I because the interval is from -1 to 1 which is two units wide..

And the other concavity:

**Notes**
It's interesting how it compares to other types of interpolation, for polynomial interpolation for example you need 3 points for a second order curve, whereas this only uses the two endpoints and has a closed form. I think that might make it computationally simpler if one has a fast way to calculate the ln and exponential functions involved...

**Future investigation**
I'd like to know whether in terms of arclength whether this curve is somehow optimal in terms of smoothness...

Quickly finding somewhat suboptimal sorting networks

It's known that the optimal sorting network for 16 entries as described here:
http://en.wikipedia.org/wiki/Sorting_network

will be between 53 and 60 compares long, the approach I describe here could only find a sorting network of 121 compares which I would call somewhat suboptimal, it would only require twice as many physical components to implement in hardware, but my code can find it quickly. It only takes a couple of minutes (in single-threaded Python) to find the 121 network for 16 entries which came out to:

[(0, 15), (1, 15), (0, 14), (2, 15), (1, 14), (0, 13), (3, 15), (2, 14), (1, 13), (0, 12), (4, 15), (3, 14), (2, 13), (1, 12), (0, 11), (5, 15), (4, 14), (3, 13), (2, 12), (1, 11), (0, 10), (6, 15), (5, 14), (4, 13), (3, 12), (2, 11), (1, 10), (0, 9), (7, 15), (6, 14), (5, 13), (4, 12), (3, 11), (2, 10), (1, 9), (0, 8), (8, 15), (7, 14), (6, 13), (5, 12), (4, 11), (3, 10), (2, 9), (1, 8), (0, 7), (9, 15), (8, 14), (7, 13), (6, 12), (5, 11), (4, 10), (3, 9), (2, 8), (1, 7), (0, 6), (10, 15), (9, 14), (8, 13), (7, 12), (6, 11), (5, 10), (4, 9), (3, 8), (2, 7), (1, 6), (0, 5), (11, 15), (10, 14), (9, 13), (8, 12), (7, 11), (6, 10), (5, 9), (4, 8), (3, 7), (2, 6), (1, 5), (0, 4), (12, 15), (11, 14), (10, 13), (9, 12), (8, 11), (7, 10), (6, 9), (5, 8), (4, 7), (3, 6), (2, 5), (1, 4), (0, 3), (13, 15), (12, 14), (11, 13), (10, 12), (9, 11), (8, 10), (7, 9), (6, 8), (5, 7), (4, 6), (3, 5), (2, 4), (1, 3), (0, 2), (14, 15), (13, 14), (12, 13), (11, 12), (10, 11), (9, 10), (8, 9), (7, 8), (6, 7), (5, 6), (4, 5), (3, 4), (2, 3), (1, 2), (0, 1)]

My approach was to compile a list of lists of every combination of 0's and 1's up to length 16, and find the longest swap necessary over all the lists, then iterate by making that swap over all the lists and then finding the next longest swap necessary, etc until all the lists are sorted. It's known by the Zero-One theorem that a network that sorts all of these lists will also sort any list of arbitrary elements...
** Notes**
If you shuffle the list of lists, it finds a different sorting network, but I haven't run it shuffled and found one better than 121, but these different 121 sorting networks might be good starting candidates for a genetic approach... Also thanks to John Owens who knew that my rough idea had to do with sorting networks and pointed me to some good references to continue...
**Source Code**
def copy(l):
    l2 = []
    for i in l:
        l2.append(i)
    return l2
def compare(t, i, j):
    if t[i] > t[j]:
        return True
    return False
def swap(t, i, j):
    if t[i] > t[j]:
        temp = t[j]
        t[j] = t[i]
        t[i] = temp
        return True
    return False
def addelement(s, a, weight, listlength):
    if len(a) < listlength:
       a1 = copy(a)
       a1.append(0)
       addelement(s, a1,weight+1, listlength)
       a2 = copy(a)
       a2.append(1)
       addelement(s, a2,weight, listlength)
    else:
        s.append([a, sorted(a)])

def bestswap(s, listlength):
    pair = [0, listlength-1]
    bestr = 0
    bestl = listlength
    best = 0
    allsorted = True
    for n in range(0, len(s)):
        if s[n][0] != s[n][1]:
            allsorted = False
    if allsorted == True:
        return [-1,-1]
    for n in range(0, len(s)):
        for l in range(0, listlength-best):
            if s[n][0][l] == 1:
                for r in range(listlength-1, l, -1):
                    if s[n][0][r] == 0:
                        if r - l > best:
                            best = r-l
                            bestl = l
                            bestr = r
    return bestl, bestr
def main():
    listlength = 16
    s = []
    a = []
    addelement(s, a,0, listlength)
    print(len(s))
    pair = [0,0]
    i = 0
    pairs = []
    while(pair != [-1,-1]):
        pair = bestswap(s, listlength)
        print(pair)
        pairs.append(pair)
        if pair != [-1,-1]:
            for j in range(0, len(s)):
                swap(s[j][0], pair[0], pair[1])
        i+=1
    print(i)
    print(pairs)
main() 

Centroid Drift Point in Polygon algorithm

Suppose you have a polygon, possibly concave, like so:

I found an algorithm that works for telling whether a point is inside the polygon or not... The first step in the reasoning is to consider the normalized vectors from the point P to the set of vertices V, those will be on a unit circle, but it will look very different depending on whether P is inside the polygon or not...

So my idea was to consider what happens when every connected pair of vertices on the polygon is replaced with the normalized midpoint of those 2 vertices...

You can see that if the point is inside the normalized polygon gets closer to a regular polygon and if the point is outside the vertices bunch together, so a way to measure that is to ask whether the centroid of the transformed polygon has moved closer to P or farther away after the midpoint operation...

A test of the algorithm...

In every case and some others I've tried it could tell whether the point was inside or outside!
** Note **
I think I thought of a counter example when the winding number exceeds 1 for a period of time.

**Source Code**
def distance(point):
    return (point[0]**2.0 + point[1]**2.0)**.5
def normal(point):
    d = distance(point)
    if d == 0:
        return [0,0]
    return [point[0]/d, point[1]/d]
def centroid(v):
    sumx = 0
    sumy = 0
    for i in range(0, len(v)):
        sumx += v[i][0]
        sumy += v[i][1]
    return [1.0*sumx/len(v), 1.0*sumy/len(v)]
def halves(v):
    v2 = []
    for i in range(0, len(v)-1):
        v2.append(normal([(v[i][0]+v[i+1][0])/2.0, (v[i][1]+v[i+1][1])/2.0]))
    v2.append(normal([(v[len(v)-1][0]+v[0][0])/2.0, (v[len(v)-1][1]+v[0][1])/2.0]))
    return v2
def pointinpoly(polygon, point):
    v = []
    for i in range(0, len(polygon)):
        v.append(normal([polygon[i][0]-point[0], polygon[i][1]-point[1]]))
    c1 = centroid(v)
    v2 = halves(v)
    c2 = centroid(v2)
    d1 = distance(c1)
    d2 = distance(c2)
    if d1 - d2 >= 0:
        return True
    else:
        return False
def main():
    polygon = [[3.22, 2.18],[4.24, 4.7],[7,5],[9.82,3.4],[7.58,.52],[6.14,2.52]]
    points = [[6, 4.68],[8.4, 4.28],[4.1,4.52],[6.97,1.04],[8.7,3.07], [4.16,2.12]]
    for i in range(0, len(points)):
        point = points[i]
        print(point, pointinpoly(polygon, point))
    
    
main()

Spearhead sort

This sort starts with the list of items:
[13, 8, 10, 18, 0, 4, 2, 11, 12, 14, 7, 19, 1, 3, 17, 6, 15, 5, 9, 16]
Starting it takes the last three items, 16, 9 and 5, sorts them, and makes a 3 item "spearhead" like below and two empty piles L and M:

It then looks at the next item from the right, 15, and compares it to the items on the spearhead and finds where it will fall, either greater than 16, or less than 5, or between 9 and 16, or between 9 and 5... Since it is between 9 and 16 it pops 16 off the spearhead and puts 16 in the M pile and replaces it with 15...

It iterates the above step all the way across the list, the next number is 6 which falls between 5 and 9, so 6 replaces 5 and 5 goes in the L pile...

The next is 17 which is greater than 15 so goes directly into the M pile:

Then 3 which is less than 6 so goes in the L pile, then 1 goes in the L pile, 19 goes in the M pile, Then 7 is between 9 and 6 so replaces 6 and 6 goes in the L pile... The only other addendum is that you try to keep the piles the same size which might change the lead number, but in this case didn't...  In that case you would just replace the appropriate trailing number with the item that would make the pile too big, and move what was there to the lead and the lead to the other trailing spot and the number that was there into the other pile, keeping the two piles balanced...

And so on until you get:

Now we can recursively use the same notion on the two smaller lists until all are in order...
** Notes**
The right to left order I used might be replaced with 3 random numbers to start and using the next random nuumber from the unsorted to prevent bad performance when the list is already sorted, for example...

A G-sort of 20 items and example code

Supposing we have a list of 20 items to be sorted, here I'll just use the numbers 0-19:
[13, 8, 10, 18, 0, 4, 2, 11, 12, 14, 7, 19, 1, 3, 17, 6, 15, 5, 9, 16]
Consider a number M for each pairwise comparison that is the distance between the numbers swapped if a swap should be made, that is that the rightmost number is smaller, for that pair or 0 otherwise.

Now I thought, what swap could be made on 10000 such random lists like the above so that the sum of the M's for that swap is the greatest over all the lists... perhaps unsurprisingly this ended up being:
[0, 19], indicating that the first and the last items of the the list should be compared and swapped to maximize the sum of the M's over all the lists, in the example above 13 would be compared to 16 and no swap would be made because 13 is already smaller than 16, but in many lists a swap would be made....

So if we have our 10000 random lists and we've already swapped [0,19], we find what should be the next swap to make the greatest sum of M's over all the lists, and iterate like that until all the lists are completely sorted, I ended up with:
[[0, 19], [1, 18], [2, 17], [3, 16], [4, 15], [5, 19], [0, 14], [1, 13], [6, 18], [7, 17], [2, 12], [5, 14], [0, 11], [8, 19], [9, 16], [1, 9], [3, 13], [6, 15], [0, 10], [10, 18], [4, 10], [5, 11], [11, 17], [8, 14], [2, 8], [12, 19], [7, 12], [0, 7], [10, 16], [3, 11], [8, 13], [13, 18], [1, 7], [9, 15], [15, 19], [3, 9], [6, 11], [11, 15], [5, 10], [2, 6], [1, 5], [14, 18], [4, 8], [0, 4], [10, 14], [6, 10], [16, 19], [12, 16], [8, 12], [14, 17], [7, 13], [3, 7], [9, 14], [5, 9], [0, 2], [2, 5], [10, 13], [7, 10], [1, 4], [13, 15], [5, 8], [12, 14], [6, 9], [9, 12], [4, 6], [8, 11], [15, 18], [17, 19], [15, 17], [6, 8], [11, 13], [3, 5], [7, 9], [10, 12], [9, 11], [16, 18], [0, 3], [14, 16], [5, 7], [2, 4], [1, 3], [13, 14], [14, 15], [12, 13], [8, 10], [3, 4], [11, 12], [18, 19], [5, 6], [4, 5], [7, 8], [6, 7], [16, 17], [15, 16], [8, 9], [10, 11], [1, 2], [2, 3], [0, 1], [17, 18], [9, 10], [13, 14], [12, 13], [5, 6], [14, 15], [7, 8], [11, 12], [3, 4], [13, 14], [1, 2], [6, 7], [8, 9], [12, 13], [10, 11], [14, 15], [9, 10]]
After these 116 compares and swaps all 10000 lists were in order. As you can see it's hard to discern a pattern after the first few swaps other than generally the items swapped get closer together, the code below is general enough that it can be used for more than 10000 lists or more or less than 20 items...

**Python Source Code**

import random
def copy(l):
    l2 = []
    for i in l:
        l2.append(i)
    return l2
def compare(t, i, j):
    if t[i] > t[j]:
        return True
    return False
def swap(t, i, j):
    if t[i] > t[j]:
        temp = t[j]
        t[j] = t[i]
        t[i] = temp
        return True
    return False
def bestswap(s, trials, listlength, sortd):
    pair = [0,0]
    best = 0
    allsorted = True
    for n in range(0, trials):
        r = copy(s[n])
        if s[n] != sortd:
            allsorted = False
    if allsorted == True:
        return [-1,-1]
    for i in range(0, listlength-1):
        for j in range(i+1, listlength):
            total = 0
            
            for n in range(0, trials):
                t = copy(s[n])
                if compare(t, i, j):
                    total += j-i    
            if total > best:
                best = total
                pair = [i,j]
    return pair
def main():
    s = []
    trials = 10000
    listlength = 20
    sortd = []
    for j in range(0, listlength):
        sortd.append(j)
        
    for j in range(0, trials):
        l = []
        for i in range(0, listlength):
            l.append(i)
        random.shuffle(l)
        s.append(l)
    bestpair = [0,listlength-1]
    i = 0
    al = []
    while(bestpair != [-1,-1]):
        i+=1
        al.append(bestpair)
        for j in range(0, trials):
            swap(s[j], bestpair[0], bestpair[1])
        bestpair = bestswap(s, trials, listlength, sortd)
        print(bestpair)
        
    print(i)
    print(al)
    
    
main()

** Update**
I let the program go over 100,000 trials and it found these 120 swaps to work over that entire assortment of lists, it took a couple of hours for the python code to run it could be much faster in other languages. So for 10,000 it took 116 swaps, for 100,000 it took 120, I figure it must not be that many more swaps for all possible lists...

[[0, 19], [1, 18], [2, 17], [3, 16], [4, 15], [5, 19], [0, 14], [1, 13], [6, 18], [2, 12], [7, 17], [5, 14], [8, 19], [0, 11], [9, 16], [1, 9], [3, 10], [10, 18], [6, 13], [4, 12], [12, 19], [8, 15], [0, 8], [5, 11], [11, 17], [7, 14], [2, 8], [1, 7], [0, 6], [6, 12], [8, 13], [13, 19], [4, 9], [9, 14], [14, 18], [3, 11], [0, 4], [10, 15], [5, 10], [12, 16], [7, 12], [1, 5], [15, 19], [3, 8], [13, 17], [2, 6], [6, 11], [10, 13], [11, 15], [4, 7], [7, 10], [8, 12], [6, 9], [16, 18], [13, 16], [0, 3], [2, 4], [3, 6], [9, 11], [11, 14], [5, 8], [17, 19], [15, 17], [12, 15], [11, 13], [8, 11], [3, 5], [5, 7], [7, 9], [1, 3], [10, 12], [12, 14], [14, 16], [8, 10], [4, 6], [6, 8], [0, 2], [18, 19], [4, 5], [6, 7], [13, 15], [16, 17], [17, 18], [15, 16], [8, 9], [3, 4], [2, 3], [5, 6], [1, 2], [0, 1], [11, 12], [9, 11], [10, 11], [12, 13], [9, 10], [14, 15], [13, 14], [7, 8], [16, 17], [11, 12], [15, 16], [3, 4], [4, 5], [2, 3], [6, 7], [8, 9], [1, 2], [16, 17], [12, 13], [5, 6], [14, 15], [10, 11], [9, 10], [7, 8], [6, 7], [13, 14], [8, 9], [10, 11], [11, 12], [5, 6]]

**UPDATE**
A professor of computer science John Owens pointed out that there are different measures of sortedness that I will try to find some improvements, and also that these are covered under the name "sorting networks" in Donald Knuth's Art of Programming books, including how to tell whether one is optimal or not, so I'll be reading that and adding more to this idea later...