http://sorting.valemak.com/odd-even/

Сортировка чёт-нечет - этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.

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

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

Сначала элементы с нечётными индексами сравниваются/обмениваются с элементами с чётными индексами (1-й со 2-м, 3-й с 4-м, 5-й с 6-м и т.д.). Затем элементы с чётными индексами сравниваются/обмениваются с соседними элементами с нечётными индексами (2-й с 3-м, 4-й с 5-м, 6-й с 7-м и т.д.). Затем снова нечётные сравниваются с чётными, потом снова чётные с нечётными и т.д. Процесс завершается если в результате двух проходов не происходило обменов — значит массив упорядочен.

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

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

static void OddEvenSort(int[] arr)
{
    bool NotSorted = true;
    int beg = 0;
    while(NotSorted)
    {
        if (beg % 2 == 1) { NotSorted = false; }
        for (int i = beg % 2; i < arr.Length; i+=2)
        {
            if (i + 1 < arr.Length)
            {
                if (arr[i] > arr[i + 1])
                {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    NotSorted = true;
                }
            }
        }
        beg++;
    }
}

Важно отметить, что необходимо проверять, чтобы i+1 не превышало размеров массива.

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