https://habrahabr.ru/post/204600/

Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. Cocktail sort) — разновидность пузырьковой сортировки. Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно перемещаются и максимумы и минимумы.

Алгоритм сортировки

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

Визуализация работы алгоритма

Реализация алгоритма

static void CocktailSort(int[] arr)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        for (int i = left; i <= right - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        right--;

        for (int i = right; i >= left + 1; i--)
        {
            if (arr[i] < arr[i - 1])
            {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
        }
        left++;
    }
}

Характеристики алгоритма