是否有一個空間高效的mergesort實現？

Question

我只是編寫了歸併這個工作版本：

static int[] merge(int[] first, int[] second){ 
    int totalsize = first.length + second.length; 
    int[] merged_array = new int[totalsize]; 
    int i = 0, firstpointer = 0, secondpointer = 0; 
    while(i < totalsize){ 
     if(firstpointer == first.length){ 
      merged_array[i] = second[secondpointer]; 
      ++secondpointer; 
     } 
     else if(secondpointer == second.length){ 
      merged_array[i] = first[firstpointer]; 
      ++firstpointer; 
     } 
     else if(first[firstpointer] < second[secondpointer]){ 
      merged_array[i] = first[firstpointer]; 
      ++firstpointer; 
     } 
     else{ 
      merged_array[i] = second[secondpointer]; 
      ++secondpointer; 
     } 
     ++i; 
    } 
    return merged_array; 
} 

static int[] mergesort(int[] array){ 

    if(array.length == 1){ 
     return array; 
    } 
    else{ 
     int length = array.length; 
     int[] first = Arrays.copyOfRange(array, 0, (int) length/2); 
     int[] second = Arrays.copyOfRange(array, (int) length/2, length); 
     return merge(mergesort(first), mergesort(second)); 
    } 

} 

但是，如果你發現，我用它創建一個新的數組，它是父陣列的某一部分的副本copyOfRange功能。在java中是否存在一個比此更具空間效率的mergesort實現？

Answer 1

重複的：How to sort in-place using the merge sort algorithm?

總結：是的，有存儲器高效合併-各種各樣，但它們是或者a）非常複雜的，或b）未時間有效：爲O（n^2 log n）的

基本上，不要打擾。這實際上並不是你存儲的那麼多的內存，如果你真的想，只需要使用quicksort。