How do I write a sort worse than O(n!)

Question

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]

Answer 1

There's a (proven!) worst sorting algorithm called slow sort that uses the “multiply and surrender” paradigm and runs in exponential time.

While your algorithm is slower, it doesn't progress steadily but instead performs random jumps. Additionally, slow sort's best case is still exponential while yours is constant.

Answer 2

Chris and I mentioned Bozosort and Bogosort in a different question.