Merge рода неспособность работать в N LogN

Question

Я написал алгоритм сортировки слиянием, но он не сортировать в журнале N. N Код для сортировки списка массива является:

void merge(int start, int mid, int end) { 
    int i,j,q; 

    for (i=start; i<=end; i++) 
     l[i]=list[i]; 

    i=start; j=mid+1; q=start; 

    while (i<=mid and j<=end) { 
     if (l[i]<l[j]) 
      list[q++]=l[i++]; 
     else 
      list[q++]=l[j++]; 
    } 

    while (i<=mid) 
      list[q++]=l[i++]; 
} 


void mergesort(int start, int end) { 
    int mid; 
    if (start<end) { 
     mid=(start+end)/2; 
     mergesort(start, mid); 
     mergesort(mid+1, end); 
     merge(start, mid, end); 
    } 
} 

Однако, если я например, номера сортировки 7800, время выполнения составляет приблизительно 1,243 мс. Тот же образец сортируется по std :: sort в 0.668 мс, и я знаю, что сортировка имеет сложность N logN. Что не так с моим кодом? Кажется, я не вижу траты времени.

Измерение времени:

#include <time.h> 

clock_t start = clock(); 

//SORTING ALGORITHM HERE// 

clock_t stop = clock(); 
double elapsed =(stop - start) * 1000.0/CLOCKS_PER_SEC; 

Answer 1

Предполагая, что ваша реализация является правильным, два O (N   LogN) не обязательно будет работать в то же количество времени. Асимптотическая сложность - это показатель того, насколько ресурсы, необходимые для запуска программы, растут по мере того, как вход становится очень большим. Просто чтобы дать вам пример, следующие циклы как O (1), так как каждый из них всегда выполняется постоянное число шагов:

for (i = 0; i < 10; i++) { 
    printf("%d\n", i); 
} 

for (i = 0; i < 1000000000; i++) { 
    printf("%d\n", i); 
} 

Но нет никаких сомнений в том, что второй будет принимать гораздо больше времени для запуска. По сути, промежуток времени между этими двумя циклами будет значительно больше, чем пробел, который вы наблюдаете для своего алгоритма сортировки, по сравнению с std::sort. Это потому, что асимптотический анализ пренебрегает константами.

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

Не говоря уже о том, что std::sort, скорее всего, не является одним алгоритмом сортировки. Вероятно, он использует разные стратегии в зависимости от размера массива. Фактически, полные реализации std::sortuse a mixture of algorithms.

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

Answer 2

В случае Visual Studio std :: sort() представляет собой комбинацию быстрой сортировки, сортировки кучи (только для предотвращения сложной ситуации с наихудшим случаем O (n^2)) и сортировки вставки, а std :: stable_sort(), представляет собой комбинацию сортировки и сортировки слиянием. Оба являются достаточно быстрыми, но можно писать более быстрый код. Пример кода в вопросе - копирование данных перед каждым слиянием, которое потребляет время. Этого можно избежать, выполняя одноразовое распределение рабочего буфера и переключая направление слияния на основе уровня рекурсии, используя пару взаиморекурсивных функций (показано ниже) или логический параметр для управления направлением слияния (не используется в примере ниже).

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

// prototypes 
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee); 
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee); 
void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee); 

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

void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    TopDownMerge(b, a, ll, rr, ee);  // merge b to a 
} 

void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    TopDownMerge(a, b, ll, rr, ee);  // merge a to b 
} 

void TopDownMerge(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 
     } 
    } 
}