Cocktail shaker sort

Сортировка перемешиванием (шейкерная сортировка или двунаправленная) — разновидность пузырьковой сортировки.

Массив просматривается поочередно справа налево и слева направо. Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения. При движении от конца массива к началу минимальный элемент «всплывает» на первую позицию, а максимальный сдвигается на одну позицию вправо.

Лучший случай для этой сортировки — отсортированный массив (O(n)), худший — отсортированный в обратном порядке (O(n^2)).

Реализация сортировки на Python:

from_future__ import print_function

def cocktail_shaker_sort(unsorted):
    """    Pure implementation of the cocktail shaker sort algorithm in Python.
    """
    for i in range(len(unsorted)-1, 0, -1):
        swapped = False

        for j in range(i, 0, -1):
            if unsorted[j] < unsorted[j-1]:
                unsorted[j], unsorted[j-1] = unsorted[j-1], unsorted[j]
                swapped = True

        for j in range(i):
            if unsorted[j] > unsorted[j+1]:
                unsorted[j], unsorted[j+1] = unsorted[j+1], unsorted[j]
                swapped = True

                if not swapped:
                    return unsorted

if __name__ == '__main__':
    try:
        raw_input          # Python 2
    except NameError:
        raw_input = input  # Python 3

    user_input = raw_input('Enter numbers separated by a comma:\n').strip()
    unsorted = [int(item) for item in user_input.split(',')]
    cocktail_shaker_sort(unsorted)
    print(unsorted)