合併排序中的閾值是多少？

Question

我無法理解合併排序的閾值，我該如何確定它。 我谷歌，但沒有結果。任何人都可以爲我解釋嗎？ 我想排序數組[50000]使用合併排序，當閾值交叉使用插入排序。

private int[] MergeSort(int[] lst) 
    { 
     int hl = lst.Length - 0; 

     if (hl < 5 || hl < 10 || hl < 15 || hl < 20 || hl < 25 || hl < 30 || hl < 35 || hl < 40 || hl < 45 || hl < 50) 
     { 
      RunTime run = new RunTime(); 
      run.X = hl; 
      InsertionSort(lst); 
      run.Ttime = Process.GetCurrentProcess().TotalProcessorTime.Milliseconds; 

       _listRunTime.Add(run); 



     } 

     if (lst.Length == 1) 
      return lst; 
     int middle = lst.Length/2; 
     int[] left = new int[middle]; 
     for (int i = 0; i < middle; i++) 
     { 
      left[i] = lst[i]; 
     } 
     int[] right = new int[lst.Length - middle]; 
     for (int i = 0; i < lst.Length - middle; i++) 
     { 
      right[i] = lst[i + middle]; 
     } 
     left = MergeSort(left); 
     right = MergeSort(right); 

     int leftptr = 0; 
     int rightptr = 0; 

     int[] sorted = new int[lst.Length]; 
     for (int k = 0; k < lst.Length; k++) 
     { 
      if (rightptr == right.Length || ((leftptr < left.Length) && (left[leftptr] <= right[rightptr]))) 
      { 
       sorted[k] = left[leftptr]; 
       leftptr++; 
      } 
      else if (leftptr == left.Length || ((rightptr < right.Length) && (right[rightptr] <= left[leftptr]))) 
      { 
       sorted[k] = right[rightptr]; 
       rightptr++; 
      } 
     } 
     return sorted; 
    } 

    private void InsertionSort(int[] arr) 
    { 
     int i, j, tmp; 
     for (i = 1; i < arr.Length; i++) 
     { 
      j = i; 
      while (j > 0 && arr[j - 1] > arr[j]) 
      { 
       tmp = arr[j]; 
       arr[j] = arr[j - 1]; 
       arr[j - 1] = tmp; 
       j--; 
      } 
     } 
    } 

我必須使用閾值而不是if (hl < 5 || hl < 10 || hl < 15 || hl < 20 || hl < 25 || hl < 30 || hl < 35 || hl < 40 || hl < 45 || hl < 50)。

Answer 1

看看這個問題，討論這個話題：Why should Insertion Sort be used after threshold crossover in Merge Sort

基本上，閾值只是一個數n，使得如果有N個要插入排序元素無序向左走排序合併後，我們切換。 n相當含糊不清，我相信你可以在你的代碼上測試它，看看哪個n優化了性能。所以不，除非您嘗試了一堆不同的值並測試性能，否則無法確定閾值編號。

順便說一句是不是你巨大的if語句完全一樣的

if(hl < 50) 

？