L'implementazione di un Mergesort senza l'utilizzo di una matrice aggiuntiva?

Question

Ho letto molto su Mergesort di recente e mi chiedo se c'è un modo per fare un Mergesort senza l'utilizzo di almeno un array aggiuntivo. E 'possibile?

Answer 1

Wikipedia è infatti possibile, ma potrebbe non produrre alcun guadagno di prestazioni:

  

L'ordinamento sul posto è possibile (ad esempio, utilizzando le liste piuttosto che array), ma è molto complicato, e offrirà piccoli miglioramenti delle prestazioni nella pratica, anche se le piste algoritmo in O ( n log < em> n ) tempo. In questi casi, algoritmi come heapsort solito offrono velocità comparabile, e sono molto meno complessa. Inoltre, a differenza della merge standard di ordinamento, sul posto merge sort non è una specie stabile. Nel caso di liste collegate l'algoritmo non usa più spazio di quello che il già utilizzato dalla rappresentazione lista, ma la O (log ( k )) utilizzato per la traccia ricorsione. Alcuni potrebbero sostenere che l'ordinamento di un elenco collegato non è a posto perché anche se si esegue l'ordinamento in data struttura dei dati, la struttura dei dati ha intrinsecamente O ( n ) dati aggiuntivi si stanno manipolando (ad esempio, i collegamenti nella lista).

Answer 2

A quanto pare, lo è. Questo documento descrive un sul posto merge sort:

  

Due sul posto varianti dell'algoritmo di mergesort classica vengono analizzati nel dettaglio. Il primo, esegue variante semplici al massimo N log 2 N + O (N) confronti e 3N log 2 N + O (N) si muove per ordinare N elementi. Il secondo, variante più avanzata richiede al massimo di log 2 N + O (n) confronti N e "N log 2 N mosse, per qualsiasi struttura fissa"? 0 e qualsiasi N? N ( "). In teoria, il secondo è superiore alle versioni avanzate di heapsort. Pratica A, a causa del sovraccarico nella manipolazione dell'indice I più veloci posto comporta mergesort ancora circa il 50 per cento più lento del heapsort bottom-up . Tuttavia, i nostri implementazioni sono pratici rispetto agli algoritmi mergesort sulla base di fusione sul posto.

Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola, "Practical In-Place Mergesort" (1996).

Answer 3

Ecco l'implementazione Java

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}
public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

Questa è la prova di unità

private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}

Answer 4

No, sarai sempre bisogno di una struttura di dati in più di fondere gli elementi ordinati a. Se non devi semplicemente essere sovrascrivendo la roba che già ordinato.