我似乎無法弄清楚爲什麼我的合併排序如此緩慢

Question

我一直在尋找所有的線程在這裏，似乎無法找到一個解決方案的工作。排序工作，但它比它應該是非常慢。下面是代碼（我工作了一個頭文件）：

#pragma once 
#ifndef DataGen_h 
#define DataGen_h 

#include "RandomSupport.h" 

void merge(long list[], long start, long mid, long end) { 
    long i = start; 
    long j = mid + 1; 
    while (j <= end && i <= mid) { 
     if (list[i] < list[j]) { 
      i++; 
     } 
     else { 
      long temp = list[j]; 
      for (long k = j; k > i; k--) { 
      list[k] = list[k - 1]; 
      } 
      list[i] = temp; 
      mid++; 
      i++; 
      j++; 
     } 
    } 
} 

void merge_sort(long list[], long startIndex, long endIndex) 
{ 
    if (startIndex >= endIndex){ 
     return; 
    } 

    long midIndex = (startIndex + endIndex)/2; 
    merge_sort(list , startIndex, midIndex); 
    merge_sort(list, midIndex + 1, endIndex); 
    merge(list, startIndex, midIndex, endIndex); 
} 




void efficientRandomSortedList(long temp[], long s) { 
    // Get a new random device 
    randomizer device = new_randomizer(); 
    // Get a uniform distribution from 1 to 1000 
    uniform_distribution range = new_distribution(1, 45000); 

    for (long i = 0; i < s; i++) { 
     // At every cell of the array, insert a randomly selected number 
     // from distribution defined above 
     temp[i] = sample(range, device); 
    } 

    // Now sort the array using insertion_sort 

    merge_sort(temp, 0, s - 1); 
} 


#endif /* DataGen_h */ 

這是類，所以不幸的是我不能改變我的工作中的數據類型。任何幫助或一般批評我的格式會有所幫助。

Answer 1

冒泡排序是一種O（n2）算法，速度很慢。合併排序是O（nlogn），它很快。

要unserstand這些算法的spees看到https://www.toptal.com/developers/sorting-algorithms

Answer 2

如果你要做merge這樣，你還不如做選擇排序;合併步驟都是二次的，而且你仍然在做對數數目的合併步驟。

就地mergesort是棘手的（而不是像mergesort一樣快）。您應該合併成一個臨時向量，然後將其複製回原始。或者在遞歸時避免通過在兩個向量之間交替進行復制。