Implémenter un mergesort sans utiliser un tableau supplémentaire?

Question

J'ai beaucoup lu récemment sur mergesort et je me demande s'il existe un moyen de faire un mergesort sans utiliser au moins un tableau supplémentaire. C'est possible?

Answer 1

Selon Wikipedia il est en effet possible, mais pourrait ne pas donner gain de performance:

Le tri sur place est possible (par exemple en utilisant des listes plutôt que des tableaux) mais est très compliqué et offrira peu de gains de performance en pratique, même si l'algorithme fonctionne en O (n log n). Dans ces cas, les algorithmes comme heapsort offrent généralement une vitesse comparable et sont beaucoup moins complexes. De plus, contrairement au tri par fusion standard, le tri par fusion sur place n'est pas un tri stable. Dans le cas de listes liées, l'algorithme n'utilise pas plus d'espace que celui déjà utilisé par la représentation de liste, mais le O (log (k)) utilisé pour la trace de récurrence. Certains soutiendraient que le tri d'une liste chaînée n'est pas en place car même si vous triez dans la structure de données donnée, la structure de données contient intrinsèquement des données supplémentaires que vous manipulez (par exemple, les liens dans la liste).

Answer 2

Non, vous aurez toujours besoin d'une structure de données supplémentaire pour fusionner les éléments triés. Sinon, vous écraserez simplement les choses que vous avez déjà triées.

Answer 3

Apparemment, c'est. This paper décrit un tri de fusion sur place:

Deux variantes en place de l'algorithme de fusion classique sont analysées en détail. La première variante directe effectue au plus N log 2 N + O (N) comparaisons et 3N log 2 N + O (N) se déplace pour trier N éléments. La seconde variante plus avancée nécessite au plus N log 2 N + O (N) comparaisons et "N log 2 N se déplace, pour tout fixe"? 0 et tout N? N (") En théorie, le second est supérieur aux versions avancées de heapsort.En pratique, en raison des frais généraux de la manipulation de l'index, notre fusion la plus rapide sur place se comporte toujours environ 50% plus lentement que l'ascendance ascendante . Cependant, nos implémentations sont pratiques par rapport aux algorithmes de mergesort basés sur en place la fusion.

Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola, "pratique in-place mergesort" (1996).

Answer 4

Voici l'implémentation 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 ++; 
     } 
    }  
} 

Voici le test unitaire

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