Самый быстрый алгоритм сортировки для определенной ситуации

Я думаю, вам нужно будет попробовать несколько примеров, чтобы увидеть, что работает лучше всего, поскольку у вас необычный набор условий. Я предполагаю, что лучше всего будет одна из

• сети сортировки
• сортировки вставки
• быстрой сортировки (один уровень - сортировка вставкой ниже)
• сортировки слиянием

Учитывая, что числа с двойной точностью относительно длинные I подозреваю, что у вас не получится лучше с сортировкой по основанию, но не стесняйтесь добавлять ее.

Как бы то ни было, Java использует быструю сортировку по двойникам до тех пор, пока количество элементов для сортировки не упадет ниже 7, при этом используется вставка Сортировать. Третий вариант имитирует это решение.

Также ваша общая проблема - досадно параллельный , поэтому вы хотите использовать параллелизм, когда это возможно. Проблема выглядит слишком малой для распределенного решения (при работе в сети будет потеряно больше времени, чем сэкономлено), но при правильной настройке ваша проблема может очень эффективно использовать несколько ядер.

Похоже, вам нужен самый простой способ сортировки 9 значений. Поскольку количество значений ограничено, я бы (как предложила Кэти) сначала выполнил сортировку с развернутой вставкой для первых 4 элементов и вторых 5 элементов. Затем я объединю эти две группы.

Вот развернутая вставка из 4 элементов:

if (u[1] < u[0]) swap(u[0], u[1]);
if (u[2] < u[0]) swap(u[0], u[2]);
if (u[3] < u[0]) swap(u[0], u[3]);

if (u[2] < u[1]) swap(u[1], u[2]);
if (u[3] < u[1]) swap(u[1], u[3]);

if (u[3] < u[2]) swap(u[2], u[3]);

Вот цикл слияния. Первый набор из 4 элементов находится в u , а второй набор из 5 элементов в v . Результат находится в r .

i = j = k = 0;
while(i < 4 && j < 5){
  if (u[i] < v[j]) r[k++] = u[i++];
  else if (v[j] < u[i]) r[k++] = v[j++];
  else {
    r[k++] = u[i++];
    r[k++] = v[j++];
  }
}
while (i < 4) r[k++] = u[i++];
while (j < 5) r[k++] = v[j++];

Хороший вопрос, потому что он сводится к вопросу "Самый быстрый способ сортировки массива из 9 элементов", а большинство сравнений и анализа методов сортировки касаются больших N. Я предполагаю, что "группы" четко определены и не играют здесь реальной роли.

Вам, вероятно, придется сравнить несколько кандидатов, потому что здесь в игру вступают многие факторы (локальность).

В любом случае, сделать его параллельным - хорошая идея. Используйте Parallel.For(), если вы можете использовать ,NET4.