Hilfe beim Verständnis von Mergesort

[babuschka]

Hallo zusammen,
ich habe eine kleine Frage zu Mergesort.

Der Algorithmus teil ja mein Array in zwei Teile. Was ist, wenn mein Array aber eine ungerade Anzahl an Elementen hat? Also z.B.: T R F H Z

Laut Code wird die Mitte wie folgt gebildet:

int mitte = (lo + (hi-lo)/2);

Wenn lo = 0 und hi = 4 wie in meinem Beispiel, müsste er also nach dem F teilen, richtig?
Bei Wikipedia ist aber ein Beispiel, bei dem er das "übrige" Element in die zweite Hälfte tut. Was mache ich falsch?

Hier der Link zum Wikipedia Bild:
http://upload.wikimedia.org/wikipedia/de/9/99/Mergesort_example.png

Gruß!!

 

[SlaterB]

aus der Berechnung von mitte alleine kann man noch nichts ablesen,
zählt das Element genau bei mitte zur ersten oder zweiten Hälfte? das entscheidet der restliche Code,

allgemein dürfte es egal sein, ob du nun 2 zu 3 oder 3 zu 2 splittest, ich glaube nicht dass das irgendwo festgelegt ist,

wenn du natürlich den Code von Wikipedia genau nachbaust, dann wäre eine Abweichung merkwürdig,
aber da musst du wie gesagt mehr Code posten + genau zum Wiki-Artikel verlinken

 

[Spacerat]

Es ist völlig egal, welche Liste (Array) die größere ist. Die andere Rechnung, wo die erste Liste länger wird, ist allerdings angehehmer:

collection.size() / 2

bzw.

array.length / 2

.
@Edit: ... angenehmer zu lesen jedenfalls. Gerade Arrays und Listen lassen sich damit aber schlechter handeln.

 

[babuschka]

Anbei der Code:

    public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

       // base case
       if (hi - lo <= 1) return;

       // sort each half, recursively
       int mid = lo + (hi - lo) / 2;
       sort(a, aux, lo, mid);
       sort(a, aux, mid, hi);

       // merge back together
       merge(a, aux, lo, mid, hi);
    }

Auszug aus: http://www.cs.princeton.edu/introcs/42sort/MergeSort.java

 

[SlaterB]

besteht eine Frage?
ich behaupte immer noch, dass der Princeton-Code nicht mit dem Wiki-Bild übereinstimmen muss

 

[babuschka]

Ich hatte mich nur gefragt, ob es wichtig ist, welcher Teil größer ist. Aber da es egal ist, bin ich zufrieden.

Danke für die Unterstützung!