Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def comparator(x, i, j):
"""Swap x[i] and x[j] if they are out of order"""
if x[i] > x[j]:
x[i], x[j] = x[j], x[i]
def oddevenmergesort(x, indexes=None):
"""In-place odd-even mergesort, applied to slice of x defined by indexes. Assumes len(x) is a power of 2. """
if indexes == None:
indexes = range(len(x))
n = len(indexes)
if n > 1:
oddevenmergesort(x, indexes[:n//2])
oddevenmergesort(x, indexes[n//2:])
oddevenmerge(x, indexes)
def oddevenmerge(x, indexes=None):
"""Assuming the first and second half of x are sorted, in-place merge. Optionally restrict to slice of x defined by indexes."""
if indexes == None:
indexes = range(len(x))
if len(indexes) == 2:
i, j = indexes
comparator(x, i, j)
return
oddevenmerge(x, indexes[::2])
oddevenmerge(x, indexes[1::2])
for i, j in zip(indexes[1::2], indexes[2::2]):
comparator(x, i, j)
sequence = [3, 9, 2, 7, 1, 5, 8, 5, 2, 7, 1, 0, 2, 7, 5, 2]
copy = list(sequence)
oddevenmergesort(copy)
assert copy == sorted(sequence)
def bitonicsort(x, indexes=None):
if indexes == None:
indexes = range(len(x))
n = len(indexes)
if n > 2:
bitonicsort(x, indexes[:n//2])
bitonicsort(x, indexes[n//2:])
dark(x, indexes)
light(x, indexes[:n//2])
light(x, indexes[n//2:])
def dark(x, indexes=None):
if indexes == None:
indexes = range(len(x))
n = len(indexes)
for i, j in zip(indexes[:n//2], indexes[::-1]):
comparator(x, i, j)
def light(x, indexes=None):
if indexes == None:
indexes = range(len(x))
n = len(indexes)
if n == 1:
return
for i, j in zip(indexes[:n//2], indexes[n//2:]):
comparator(x, i, j)
light(x, indexes[:n//2])
light(x, indexes[n//2:])
sequence = [3, 9, 2, 7, 1, 5, 8, 5, 2, 7, 1, 0, 2, 7, 5, 2]
copy = list(sequence)
bitonicsort(copy)
assert copy == sorted(sequence)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.