이것은 mergesort의 적절한 구현입니까?

Question

모든 재귀 단계마다 3 개의 배열을 작성하는 것이 너무 많은 공간을 차지할 수 있다고 생각하지만 실제로 다른 방법을 찾아 낼 수는 없습니다. 제발 뭐가 잘못 됐는지 말해줘.

public static int[] split(int [] vector){ 

    if(vector.length <= 1 || vector == null) 
     return vector; 
    int len = vector.length; 

    int[] list1 = new int[len/2]; 
    // If the number of elements is odd the second list will be bigger 
    int[] list2 = new int[len/2 + (len % 2)]; 

    // Here we assign the elements to 2 separate lists 
    for(int x = 0; x < len/2; x++) 
     list1[x] = vector[x]; 
    for(int j = 0, i = len/2; j < list2.length; i++, j++) 
     list2[j]=vector[i]; 

    // Apply the recursion, this will eventually order the lists 
    list1 = split(list1); 
    list2 = split(list2); 

    // Here we take the 2 ordered lists and merge them into 1 
    int i = 0, a = 0, b = 0; 
    int[] listfinal = new int[len]; 
    while(i < len){ 
     if(a >= list1.length){ 
      listfinal[i] = list2[b]; 
      b++; 
     } else if(b >= list2.length){ 
      listfinal[i] = list1[a]; 
      a++; 
     } else if(list1[a] <= list2[b]){ 
      listfinal[i] = list1[a]; 
      a++; 
     } else if(list1[a] > list2[b]){ 
      listfinal[i] = list2[b]; 
      b++; 
     } 
     i++; 
    } 
    return listfinal; // Return the merged and ordered list 
} 

Answer 1

mergesort를 수행하기 위해 둘 이상의 임시 배열을 만들 필요는 없습니다. 여러분이 잘못하고있는 것은 배열을 복사하여 재귀 적 호출로 전달하는 것입니다. 대신 원래 배열을 전달해야합니다.

JDK에서 mergesort를 구현하는 데 유익한 정보가 될 수 있습니다. 라인 1146은 Arrays.java입니다.

Answer 2

최상위 수준의 입력 크기와 동일한 배열 하나를 할당하고 모든 재귀에 대해 다시 사용하는 코드입니다. 백만 개의 정수에서 이것은 내 컴퓨터에서 약 300ms가 걸리고 Java 라이브러리 정렬에는 230ms가 걸립니다. 튜닝 노력이 필요 없으니 ...

// Sort the elements of a between lo and hi inclusive. 
private static void sortImpl(int [] a, int lo, int hi, int [] tmp) { 

    if (hi <= lo) return; 

    // Recur on sublists. 
    int mid = (hi + lo)/2; 
    sortImpl(a, lo, mid, tmp); 
    sortImpl(a, mid + 1, hi, tmp); 

    // Move past items already in the right place. 
    int t1 = lo; 
    while (a[t1] < a[mid + 1]) t1++; 

    // Merge sublists into result. 
    int p1 = t1; 
    int p2 = mid + 1; 
    int i = t1; 
    System.arraycopy(a, t1, tmp, t1, mid - t1 + 1); 
    while (p1 <= mid) 
     a[i++] = (p2 > hi || tmp[p1] < a[p2]) ? tmp[p1++] : a[p2++]; 
} 

public static void sort(int [] a) { 
    sortImpl(a, 0, a.length - 1, new int[a.length]); 
}