Creates a sequence of compare-swap operations that perform a sort.

gen_sort.py

#!/usr/bin/python3
import sys

# Returns a list of compare-swap tuples that merges two lists
def gen_merge(a, b):
    return [(x, y) for x in a for y in b]            

# Returns a list of compare-swap tuples that performs a merge sort
# Generates n^2/2 - n/2 = O(n^2) compare-swaps
def gen_sort(l):
    n = len(l)

    if n <= 1:
        # No comparisons are required to sort less than one element
        return []

    if n == 2:
        # Comparisons to sort two elements
        return [(l[0], l[1])]
    
    m = n // 2
    left, right = l[:m], l[m:]
    # Comparisons to sort the left segment
    cmp_left = gen_sort(left)
    # Comparisons to sort the right segment
    cmp_right = gen_sort(right)
    # Comparisons to do the merge
    cmp_merge = gen_merge(left, right)
    return cmp_left + cmp_right + cmp_merge

def main():
    if len(sys.argv) != 2:
        sys.exit("Number of elements expected")

    n = int(sys.argv[1])
    for x, y in gen_sort(range(0, n)):
        print("cmp_swap(" + str(x) + ", " + str(y) + ")")

if __name__ == "__main__":
    main()