Was an Ort sortieren, wenn zwei Arrays in Ordnung sind?

Question

I am working on this question. Meine Funktion Prototyp ist

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

Im 2. Teil der Funktion ich weiß leftPos zu leftPos + (rightPos-leftPos)/2 und (rightPos-leftPos)/2 bis rightPos werden in der Reihenfolge sortiert.

Ich habe versucht, darüber nachzudenken, wie ich an Ort und Stelle tun könnte, zu wissen, dass die zwei Teile in Ordnung sind. Ich konnte mir keine vorstellen. Ich schaute auf die Merge-Funktion auf merge sort, aber es verwendet ein Ausgabe-Array statt an Ort und Stelle.

Wie sortiere ich es in dem Wissen, dass beide Scheiben in Ordnung sind?

Hinweis: Ich dachte, ich könnte ein zusätzliches Array übergeben, das die gleiche Länge wie das Haupt-Array zur Verwendung als temporärer Speicher hat, aber die Art, an die ich dachte, würde mich dazu zwingen, Array.Copy nach jeder Zusammenführung zu tun.

Answer 1

In-Place-Merge ist möglich, aber es ist kompliziert und bringt nicht viel Leistungsgewinn. Unten ist ein Beispielcode von here. from ist Ihr leftPos, to ist Ihr rightPos, pivot ist Ihr (rightPos-leftPos)/2 und die Längen sind die Längen jeder Hälfte.

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); 
}