Bogosort

Сегодня на собеседовании (я всё ещё ищу пайтонистов, ау) всплыли алгоритмы сортировки и я решил немного почитать на эту тему. Оказывается есть смешной алгоритм сортировки Bogosort, который на практике не применяется, а служит только иллюстративным целям:

Bogosort (также рандомная сортировка, сортировка ружья или обезьянья сортировка) является очень неэффективным алгоритмом сортировки. Её используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то подбросить колоду в воздух, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода.

Я, для интереса, написал его на Пайтоне и поразвлекался с запускам на разных данных. Вот код, если интересно:

from random import shuffle
from itertools import izip, islice

def bogosorted(arr):
    for x, y in izip(islice(arr, 1, None), islice(arr, 0, len(arr) - 1)):
         if y > x: return False

    return True

def bogosort(arr):
    while arr and not bogosorted(arr):
        shuffle(arr)

    return arr


print bogosort([1, 1, 3, 2, 2, 2])