Какая сортировка самая быстрая?

Question

[Fear1]

Если я все правильно понимаю, а зачастую все происходит наоборот...
У меня есть массив из 100 000 элементов, каждый из них это случайное число от 1 до 100 000;

С помощью какого (из известных вам) алгоритма можно отсортировать весь этот массив за самое короткое время?

И самый главный вопрос:
Какое время потребуется алгоритму для решения этой задачи?
Просьба не отвечать ответом, подобным на (n log n), (n^2) и т.д. Нужно конкретное время, что бы убить недопонимание в себе.

P.S. Заранее спасибо за терпеливость к данным вопросам.

Answer 1

[Mrrl]

Если есть память на ещё один массив из 100000 элементов, то быстрее всего будет работать сортировка подсчётом:

void CountSort(int *A1,int *A2,int L,int Nmax){
for(int i=0;i<=Nmax;i++) A2[i]=0;
for(int i=0;i < L;i++) A2[A1[i]]++;
int s=0;
for(int i=0;i<=Nmax;i++) for(int j=0;j < A2[i];j++) A1[s++]=i;
}

Здесь A1 - сортируемый массив, A2 - дополнительный массив длиной Nmax+1.
У меня получилось среднее время 0.88 миллисекунды. Для сравнения, std::sort даёт на тех же примерах 7.2 миллисекунды - в 8 раз больше.
Возможно, радикс-сортировка по модулю 256 даст ещё меньшее время (она не так агрессивно работает с памятью). Но она в 4 строчки не уместится.

Comments

[Mrrl]

Радикс-сортировка дала 1.5 миллисекунды. Но ей нужно гораздо меньше памяти - меньше 4 килобайт (достаточно 2 массивов по 400 элементов).

Answer 2

[wyvan]

Годная статья на этот счет:
habrahabr.ru/post/204600/