배열이 두 개일 때 정렬이 어떻게됩니까?

Question

I am working on this question. 내 함수 프로토 타입은 내가 leftPos + (rightPos-leftPos)/2 (rightPos-leftPos)/2 rightPos에이 순서로 정렬됩니다에 leftPos을 알고있는 함수의 두번째 부분에서

static void Sort(byte[] arr, int leftPos, int rightPos) 

입니다.

나는 두 부분이 순서대로되어 있음을 알기에 내가 어떻게 할 수 있는지 생각해 보았다. 나는 어떤 것도 생각할 수 없었다. merge sort에서 병합 함수를 살펴 봤지만 대신 출력 배열을 사용합니다.

두 조각이 모두 순서대로 정렬되어 있는지 어떻게 알 수 있습니까?

참고 : 기본 배열과 동일한 길이의 여분의 배열을 임시 메모리로 사용할 수 있지만 각 병합 후에 Array.Copy를 수행해야한다고 생각했습니다.

Answer 1

현재 위치에서 병합이 가능하지만, 복잡하고 많은 성능 향상을 얻지 못합니다. 다음은 here의 샘플 코드입니다. from은 leftPos, to은 rightPos, pivot은 (rightPos-leftPos)/2이며 길이는 각 절반의 길이입니다.

void merge(int from, int pivot, int to, int len1, int len2) { 
    if (len1 == 0 || len2==0) return; 
    if (len1+len2 == 2) { 
    if (compare(pivot, from) < 0) 
    exchange(pivot, from); 
    return; 
    } 
    int first_cut, second_cut; 
    int len11, len22; 
    if (len1 > len2) { 
    len11=len1/2; 
    first_cut = from + len11; 
    second_cut = lower(pivot, to, first_cut); 
    len22 = second_cut - pivot; 
    } else { 
    len22 = len2/2; 
    second_cut = pivot + len22; 
    first_cut = upper(from, pivot, second_cut); 
    len11=first_cut - from; 
    } 
    rotate(first_cut, pivot, second_cut); 
    int new_mid=first_cut+len22; 
    merge(from, first_cut, new_mid, len11, len22); 
    merge(new_mid, second_cut, to, len1 - len11, len2 - len22); 
}