Почему вставка сортируется быстрее, чем слияние?

Question

Я создал на jsperf.com тест для 3 методов сортировки: Bubble, Insertion и Merge. Link

Перед испытанием я создаю несортированный массив со случайным числом от 0 до 1Mln. Каждый раз, когда тест показывает, что Insertion сортируется быстрее, чем Merge one. Что причина такого результата, если время сортировки слияния O (п журнала (п)), тогда как вставки и Bubble сорт имеет O (N^2) test result here

Answer 1

Без дополнительной проверки, предварительный ответ:

Ваших сортировка вставки довольно оптимизирована - вы только переключаете элементы. Ваша сортировка слияния создает новые массивы с использованием [] и создает новые массивы с использованием slice и concat, что является большой нагрузкой на управление памятью, не говоря уже о том, что concat и slice имеют неявные циклы внутри них (хотя в собственном коде). Сортировка слияния эффективна, когда она выполняется на месте; с полным копированием происходит, что должно сильно замедлить вас.

Answer 2

Как прокомментировал Амадан, было бы лучше, если бы сортировка слияния выполняла однократное распределение того же размера, что и отсортированный массив. Сверху сортировка слияния использует рекурсию для генерации индексов, используемых слиянием, тогда как снизу вверх пропускает рекурсию и использует итерацию для генерации индексов. Большая часть времени будет потрачена на фактическое слияние суб-массивов, поэтому избыточные накладные расходы сверху вниз на более крупные массивы (1 миллион элементов или более) составляют всего около 5%.

Пример кода C++ для несколько оптимизированного сортировки слияния снизу вверх.

void MergeSort(int a[], size_t n)   // entry function 
{ 
    if(n < 2)        // if size < 2 return 
     return; 
    int *b = new int[n]; 
    BottomUpMergeSort(a, b, n); 
    delete[] b; 
} 

size_t GetPassCount(size_t n)    // return # passes 
{ 
    size_t i = 0; 
    for(size_t s = 1; s < n; s <<= 1) 
     i += 1; 
    return(i); 
} 

void BottomUpMergeSort(int a[], int b[], size_t n) 
{ 
size_t s = 1;        // run size 
    if(GetPassCount(n) & 1){    // if odd number of passes 
     for(s = 1; s < n; s += 2)   // swap in place for 1st pass 
      if(a[s] < a[s-1]) 
       std::swap(a[s], a[s-1]); 
     s = 2; 
    } 
    while(s < n){       // while not done 
     size_t ee = 0;      // reset end index 
     while(ee < n){      // merge pairs of runs 
      size_t ll = ee;     // ll = start of left run 
      size_t rr = ll+s;    // rr = start of right run 
      if(rr >= n){     // if only left run 
       rr = n; 
       BottomUpCopy(a, b, ll, rr); // copy left run 
       break;      // end of pass 
      } 
      ee = rr+s;      // ee = end of right run 
      if(ee > n) 
       ee = n; 
      // merge a pair of runs 
      BottomUpMerge(a, b, ll, rr, ee); 
     } 
     std::swap(a, b);     // swap a and b 
     s <<= 1;       // double the run size 
    } 
} 

void BottomUpCopy(int a[], int b[], size_t ll, size_t rr) 
{ 
    while(ll < rr){       // copy left run 
     b[ll] = a[ll]; 
     ll++; 
    } 
} 

void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;       // b[]  index 
    size_t l = ll;       // a[] left index 
    size_t r = rr;       // a[] right index 
    while(1){        // merge data 
     if(a[l] <= a[r]){     // if a[l] <= a[r] 
      b[o++] = a[l++];    // copy a[l] 
      if(l < rr)      // if not end of left run 
       continue;     //  continue (back to while) 
      while(r < ee)     // else copy rest of right run 
       b[o++] = a[r++]; 
      break;       //  and return 
     } else {       // else a[l] > a[r] 
      b[o++] = a[r++];    // copy a[r] 
      if(r < ee)      // if not end of right run 
       continue;     //  continue (back to while) 
      while(l < rr)     // else copy rest of left run 
       b[o++] = a[l++]; 
      break;       //  and return 
     } 
    } 
}