MergeSort den Merge Teil nicht verstanden

[BookOfLove]

Ich bin dabei, den Sortieralgorithmus MergeSort zu verstehen. Eine Stelle, die ich nicht nachvollziehen konnte, war die Folgende.

package de.vogella.algorithms.sort.mergesort;

public class Mergesort {
  private int[] numbers;
  private int[] helper;

  private int number;

  public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
  }

  private void mergesort(int low, int high) {
    // check if low is smaller then high, if not then the array is sorted
    if (low < high) {
      // Get the index of the element which is in the middle
      int middle = low + (high - low) / 2;
      // Sort the left side of the array
      mergesort(low, middle);
      // Sort the right side of the array
      mergesort(middle + 1, high);
      // Combine them both
      merge(low, middle, high);
    }
  }

  private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
      helper[i] = numbers[i];
    }

    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
      if (helper[i] <= helper[j]) {
        numbers[k] = helper[i];
        i++;
      } else {
        numbers[k] = helper[j];
        j++;
      }
      k++;
    }
  [B]  // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
      numbers[k] = helper[i];
      k++;
      i++;[/B]
    }

  }
}

Quelle: HIER

Warum wird beim Einsortieren der 2 Hälften angenommen, dass das Verfahren Lücken nur beim ersten Teil haben wird?(Ab Zeile 52)
Hätten wir solche 2 Hälften: {5,15}/{10,20}
Hätten wir nicht bei der rechten Hälfte die Lücke?

Dank im Voraus

 

[ice-breaker]

Das ist ganze einfach verstanden, wenn du es auf dem Papier mal schrittweise durchgehst:

Die Idee dieser Implementierung ist einfach, den linken Merge als Basis zu nehmen und in das Result zu packen und mit dem rechten aufzufüllen, wenn in eine Lücke noch ein Wert reinpasst. Nun ergeben sich einfach folgende Fälle:

• beide Teile haben noch Einträge mehr: kein Problem, es wird die Merge-Logik angewendet
• der rechte Teil hat keine Elemente: kein Problem, es wird einfach mit der Merge-Logik weitergemacht und bei jeder Prüfung wird festgestellt dass der rechte Merge kein passendes Element für die Lücke hat (da es leer ist)
• der linke hat keine Elemente mehr: es können einfach alle Teil vom rechten Teil in das Ergebnis kopiert werden

Wie beim Verständnis aller Algorithmen gilt: Spiele einfach mal alle möglichen Fälle mit einem Stift und Papier mal durch, da bekommst du sehr schnell mit, wenn du irgendwo noch etwas nicht verstanden hast.