I wrote an O(n!) sort for my amusement that can't be trivially optimized to run faster without replacing it entirely. [And no, I didn't just randomize the items until they were sorted].
How might I write an even worse Big-O sort, without just adding extraneous junk that could be pulled out to reduce the time complexity?
http://en.wikipedia.org/wiki/Big_O_notation has various time complexities sorted in growing order.
Edit: I found the code, here is my O(n!) deterministic sort with amusing hack to generate list of all combinations of a list. I have a slightly longer version of get_all_combinations that returns an iterable of combinations, but unfortunately I couldn't make it a single statement. [Hopefully I haven't introduced bugs by fixing typos and removing underscores in the below code]
def mysort(somelist): for permutation in get_all_permutations(somelist): if is_sorted(permutation): return permutation def is_sorted(somelist): # note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf) if (len(somelist) <= 1): return True return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:])) def get_all_permutations(lst): return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]