Diskussion:Mergesort

Kann bitte jemand mit Sysop-Rechten diesen Artikel nach MergeSort verschieben, damit wir innerhalb der Wikipedia eine einheitliche Schreibweise haben? --Head 11:09, 31. Aug 2003 (CEST)

Weblink nicht verfügbar

Der Link zu den Java-Beispielen führt zu folgendem Fehler:

Proxy Error
The proxy server received an invalid response from an upstream server.
The proxy server could not handle the request GET /~staerk/algorithms/SortAnimation.html.
Reason: Could not connect to remote machine: Connection refused

Bitte beheben oder den Link entfernen. --Herrn 12:30, 1. Nov 2004 (CET)

Anmerkung eines Lesers

Hallo Leser ... bitte solche Bemerkungen eher auf die Diskussionsseite legen. Das Problem war die Frage, ob der Merge-Schritt innerhalb oder ausßerhalb der Abbruchbedingung liegen soll. Ich hab's mir grad nochmal angeschaut. Ich denke der Merge-Schritt ist schon richtig so (Sedgewick hat's genauso). Mir würde auch kein Grund einfallen, warum er außerhalb sein sollte. Denn die Befehle im if-Ausdruck werden nur ausgeführt, wenn auch wirklich was zum Mischen da ist ... oder? Grüße --Jkrieger 20:47, 5. Sep 2005 (CEST)

Pascal-Implementierung

Ohne dem Entwickler der P-Impl. näher treten zu wollen, aber ich denke dieser Code sollte wirklich überarbeitet werden. Zunächst ist das gar kein reines Pascal, sondern Delphi, und zum zweiten ist der Code so GARNICHT modular. Er sortiert Elemente auf ner GUI!!! Werde mich in den nächsten Tagen mal dran machen wenn ich Zeit habe.

Was sagt Ihr? --ZOiDberg 01:03, 6. Mär 2006 (CET)

Pascal-Implementierung ... Fortsetzung

Ja, stimmt - Sedgewick hat es GENAUSO FALSCH. Wie weiter unten schon steht, in dieser Form ist der Algorithmus NICHT stabil. Es fehlt eine zusätzliche Prüfung beim Mischen, die bei gleichen Werten entscheidet, ob der obere oder der untere Fall verwendet werden muß.

Stabilität

Hallo,

ich möchte nur mal anmerken, dass Mergesort an sich nicht stabil ist. Die Stabilität hängt im Wesentlichen vom bitonischen Mischverfahren ab. Man kann das Verfahren auch stabil implementieren, jedoch ist das nirgends erwähnt. Ich weiss jetzt auch nicht an welcher Stelle man das im Text erwähnen sollte, deswegen hab ichs nicht reingeschrieben.--Hackendahl 16:08, 26. Mai 2006 (CEST)

Ich habe noch nie von einer instabilen Variante von Mergesort gehört. Die folgende Vergleichslogik ergibt bei Mergesort immer eine stabile Sortierung.

A = Element 1
B = Element 2
C = Ergebnis

Wenn A > B dann C=B andernfalls C=A

Ebenfalls funktionieren würde (aber langsamer)...

Wenn A <= B dann C=A andernfalls C=B

--31.17.34.192 15:59, 12. Jul. 2022 (CEST)

neue Pascal-Implementierung

Ich habe mir erlaubt, eine reine Pascal-Implementierung reinzusetzen. Da Standard-Pascal kein "array of integer" kennt, habe ich auch die Typvereinbarungen mit hinzugefügt. Falls das nicht üblich ist, kann das auch wieder gelöscht werden. Ich denke aber diese Vereinbarungen und der Unterprogrammaufruf sind hilfreich zum Verständnis. So ist es ein sofort lauffähiges und funktionsfähiges Programm. Als Quelle hab ich das Standardwerk "Algorithmen" von Robert Sedgewick benutzt, die Implementation hab ich selber geschrieben. -- 134.109.108.159

Bemerkung: Sehe gerade, dass die iterative Formulierung sowohl bei Java als auch bei Pascal steht, das sollte man besser aus dem Quellcode-Bereich ausgliedern, evtl. genauso wie die Bemerkung zum Aufbau des temporären Feldes (falls das in allen Programmiersprachen so gemacht wird) -- 134.109.108.159

Out-Of-Place

Eine Begründung, warum ein temporäres Array beim Mischen benötigt wird, wäre wünschenswert. Vielleicht komme ich demnächst auch selbst dahinter...

Also eine anständige Begründung weiss ich gerade auch nicht. Wir wollen in O(n) zwei bereits sortierte, etwa gleichlange Listen (Liste0, Liste1) so bearbeiten, daß im Ergebnis wieder beide Listen jeweils für sich sortiert sind, aber das erste Element von Liste1 grössergleich dem letzten Element von Liste0 ist. Also mir fällt nix besseres ein, als eine der beiden Listen irgendwo zwischenzuspeichern, und dann ganz normal zu mergen (also evtl. nur 50% Tempspeicher, nicht unbedingt 100%, wie im Artikel beschrieben). Hat jemand eine bessere Idee? --77.8.122.147 08:02, 13. Dez. 2011 (CET)

Naja, wenn man 2 bereits sortierte (Teil-) Listen hat, kann man die gegebene Sortierung sicherlich dazu nutzen, ein exaktes "Mittenelement" der zusammenzufügenden Liste zu ermitteln. Somit kann man, ohne weiter drüber nachzudenken, die Elemente genau passend zur gegebenen Teilung aufteilen (wie bei Quicksort erwünscht), und diese, wenn nichts besseres in den Sinn kommt, einfach nochmal sortieren. Das widerlegt die Behauptung. --77.8.120.155 20:14, 16. Jul. 2014 (CEST)

Wenn du das mit nur einem Array versuchst, werden an zwei stellen Plätze frei, aber du willst ja nur einen neuen Array haben. man könnte natürlich ständig den halben Array hinundher kopieren, aber das ist so langsam wie Insertionsort --129.13.186.1 22:33, 20. Jun. 2008 (CEST)

Ich halte die out-of-place Behauptung für "üble Nachrede". Guter Text mit viel Erklärung und Implementierung: http://www.linux-related.de/index.html?/coding/sort/sort_merge.htm --Chricho 22:10, 21. Sep. 2009 (CEST)

Und auch im genannten Link ist Mergesort Out-Of-Place und zwar deshalb, weil es unmöglich ist, zwei benachbarte Listen In-Place zusammenzurechnen, ohne dabei irgendeine Art von Zwischenspeicher zu verwenden.

Beispiel:

Liste A: 5,6,7,8,9

Liste B: 0,1,2,3,4

Was soll denn mit der 5 aus Liste A passieren, wenn sie mit der 0 aus Liste B überschrieben wird? Aus diesem Grund werden Liste A und B in Liste C (Out-Of-Place) zusammengerechnet. --31.17.34.192 16:40, 12. Jul. 2022 (CEST)

Hinweis: Quellcode PHP

Ich habe mir gerade den Quellcode für PHP durchgelesen.

Wenn ich mich nicht irre, sollte man auch den Array "$multiMergeStorage" als Global setzen (damit man auf ihn von Außerhalb der Funktion zugreifen kann).

Wenn ich mich irre, Sorry :)

Haskell-Version

Ich finde es ungünstig, die Standardfunktion splitAt zu benutzen. Dadurch wird der Algorithmus nicht in seiner Gesamtheit dargestellt. Man sollte es durch eine selbstdefinierte split-Funktion ersetzen. -- Xyan 03:22, 26. Aug 2006 (CEST)

die zweite version funktioniert nicht für listen der länge 0. sie ist falsch! hier eine korrektur

mergeSort:: Ord a => [a] -> [a]
mergeSort l@(x:y:ys) = merge (mergeSort (take ((length l) `div` 2) l)) (mergeSort (drop ((length l) `div` 2) l))
	           where
		   merge l@(x:xs) r@(y:ys) = if (x <= y) then x:merge xs r else y:merge l ys
		   merge a b = a++b
mergeSort x = x

zu viele Implementierungen

Ich finde es etwas überflüssig (und auch unübersichtlich), dass so viele verschiedene Implementierungen in dem Artikel vorgestellt werden. Ich finde, dass eine Pseudocode oder Java vollkommen ausreichen würde. Schließlich müsste man der jetztigen Vorgehensweise zufolge für jede halbwegs verbreitete Sprache eine Implementierung zeigen, was den Rahmen des Artikels mehr als sprengen würde. IMO ist das ein klarer Fall für die Wikibooks. Ein Wikibook Implementierung von Sortieralgorithmen wär sicher nicht das ware, aber dafür könnte vielleicht in den Wikibooks zu den entspr. Sprachen ein neues Kapitel "Implementierung typischer Algorithmen" eröffnet werden, auf diese dann dieser Artikel verweist. --87.78.90.44 23:40, 28. Aug 2006 (CEST)

Korrektheitsbeweis

Der Beweis ist trivial und dennoch hier eindeutig falsch!

Iterative Implementierung

Sowohl der normale als auch der natürliche Mergesort lassen sich auch vollständig iterativ programmieren. Wenn ich demnächst mal Zeit hab, kann ich mal ein Java-Beispiel für den iterativen natürliche Merge-Sort angeben.

Außerdem wärs noch ganz hilfreich zu erwähnen, dass der Verschmelz-Schritt auch gut parallelisierbar ist (Jeder Rechner bekommt ein eigenenes Paar von Unterlisten), jedenfalls bis auf die letzten Verschmelzschritte.

Ansonsten sollte nochmal jemand daraufhinweisen, dass der normale Mergesort nur Listen mit 2^n Elementen verarbeiten kann. Listen mit anderen Größen müssen zuvor erst aufgefüllt werden.

1. Sollte man definitiv stärker drauf hinweisen. Insbesondere funktioniert Mergesort dan auch in-place und ist für viele Dinge wesentlich besser geeignet als Quicksort. (man braucht noch nicht einmal den Stack vom Quicksort)
2. Siehe STL-Parallel (gcc-Implementierung) und STXXL, da werden parallelisierte Mergesorts effektiv implementiert.
3. Ist doch Unsinn. Beim rekursiven Mergesort klappt das durch Rundung. Dann hat man ab und zu eben Teilfelder mit verschiedener Anzahl zu mergen. Beim iterativen Mergesort klappt das durch eine einfache zusätzliche Bedingung, die eine Bereichsüberschreitung verhindert. Von einer vorherigen Verlängerung habe ich noch nie etwas gehört. --Chricho 11:13, 28. Aug. 2009 (CEST)

Ausufernde Implementierungslisten

Hallo zusammen!

Ich wäre dafür alle Implementierungen bis auf (sagen wir) max. drei zu löschen ... die Wikipedia ist ja schließlich kein Code-Repository, sondern eine Enzyklopädie. Ich denke es würde Java oder C, Pascal und Haskell reichen ... oder evtl. sogar nur Pseudocode? Die Java-Implementierung für Listen ist evtl. noch sinnvoll, aber ich denke ein einfach zu lesender Pseudocode oder Pascal (finde ich noch am besten zu lesen) würde vollkommen ausreichen. Eine iterative Implementierung fände ich schön ... evtl. auch in Pascal/Pseudocode?

Ich schlage einfach mal folgenden Pascal-Code vor. Was meint ihr?

  { N: länge des Feldes a[1..N], das sortiert werden soll }

  procedure merge(links:integer, mid:integer, rechts:integer);
  var i,j,k:integer;
      b: array[links..rechts] of datatype;
  begin
    { Mischen der sortierten Unterfelder
      dabei wird ein Hilfsfeld b verwendet
        1. Daten in Hilfsfeld kopieren }
    for i:=mid downto links do 
      b[i] := a[i];
    for j:=mid+1 to rechts do 
      b[rechts+mid+1-j] := a[j];
    
    {      Die Felder sind jetzt in b[] so angeordnet, dass sich die
           jeweils größten Elemente in der Mitte befinden
           i und j zeigen auf auf den linken, bzw. rechten Rand
  
         2. Mischen: }
    for k:=links to rechts do
      if b[i]<b[j] then begin
        a[k]:=b[j];
        i:=i+1;
      end else begin
        a[k]:=b[j];
        j:=j-1;
      end;
  end;

  procedure mergesort(links:integer, rechts:integer);
  var mid:integer;
  begin
    if (rechts-links>0) then begin { Abbruchbedingung für Rekursion }
      { Mittleres Element bestimmen und rekursiver Abstieg }
      mid := (rechts+links) div 2; 
      mergesort(links, mid);
      mergesort(mid+1, rechts);
    
      merge(links, mid, rechts);
    end;
  end;

Außerdem sind da ein paar Sachen zum merge-Schritt zwischen die Code-Beispiele gerutscht. Viele Grüße und frohes Fest, --Jkrieger 19:57, 24. Dez. 2006 (CET)

Komplexität

Müsste man nicht neben der Zeitkomplexität auch noch die Operationenkomplexität W(n) angeben? Das wäre dann doch O(log(n)log(log(n))) oder täusche ich mich da?

Java-Implementierung

Ich habe mal die Java-Implementierung durch eine andere ersetzt [1], die nicht ständig neue Arrays anlegt und überflüssigerweise in der Aufteilphase Daten kopiert. Das bringt bei mir (bei den Größen, die ich im Hauptspeicher testen kann) etwa einen Faktor 2 bis 3. -- Paul E. 18:10, 30. Jan. 2007 (CET)

Ruinöser Pascal-Abschnitt

Ich habe diese Ruine jetzt erstmal aus dem Artikel entfernt. Falls sich jemand berufen fühlt, eine saubere Pascal-Implementation zu erstellen (was angesichts der ohnehin schon im Überfluss vorhandenen Alternativen in anderen Sprachen m.E nicht notwendig ist), so kann er die vorherige Version ja noch im Archiv begutachten: http://de.wikipedia.org/w/index.php?title=Mergesort&oldid=27481785#Pascal

-- Matthias/213.168.121.143 00:51, 12. Feb. 2007 (CET)

Java(-Listen)-Implementierung

Ich hab 3 fehlende static in der Java-Listen Implementierung ergänzt. Außerdem finde ich beide Java-Implementierung etwas unschön und füge daher hier für Freunde des kurzen, kommentarlosen, englischen Codes entsprechende Versionen an.

Hmm, wenn ich das richtig sehe, besteht (bei der array-Variante, die andere habe ich mir nicht angesehen) der Unterschied eigentlich nur darin, dass die Variablennamen verkürzt und die Kommentare entfernt wurden. Ich sehe nicht wirklich, inwieweit das schöner ist ... - es hilft jedenfalls IMHO nicht, das Verständnis des Algorithmus (bzw. seiner Implementation) zu fördern. -- Paul E. 16:43, 20. Feb. 2007 (CET)

Falls sich jemand mit den Code-Konventionen der Wikipedia auskennt kann er das gerne entsprechend in den Artikel migrieren.

Java-Array-Implementierung

public static int [] mergesort(int [] a){
	    int[] t = new int[a.length];
	    int[] h = new int[a.length];   
	    mergesort(a, t, h, 0, a.length);
	    return t;
	}
	
	private static void mergesort(int[] a, int[] t, int[] h, int min, int max)
	{
	    if ((max - min) > 1) {
	        int mid = (min + max) / 2;
	        mergesort(a, h, t, min, mid);
	        mergesort(a, h, t, mid, max);
	        merge(h, t, min, mid, max);
	    }
	    else {
	        t[min] = a[min];
	    }
	}
	
	private static void merge(int[] s, int[] t, final int min, final int mid, final int max) {
	    int i = min;
	    int left = min;
	    int right = mid;
	
	    while (left < mid && right < max){
	        if (s[left] <= s[right]){
	            t[i] = s[left];
	            left++;
	            i++;
	        } else {
	            t[i] = s[right];
	            right++;
	            i++;
	        }
	    }
	    
	    while (left < mid) {
	        t[i] = s[left];
	        left++;
	        i++;
	    }
	
	    while (right < max){
	        t[i] = s[right];
	        right++;
	        i++;
	    }    
	}

Java-Listen-Implementierung

class QueueNode {
	int val;
	QueueNode next;
	public QueueNode(int val) {
		this.val = val; 
		next = null;
	}
	public boolean lessOrEqual(QueueNode a) {
		return (val <= a.val);
	}
}

	public static QueueNode nThNode(QueueNode start, int n) {
		QueueNode p = start;
		for (int i = 0; i < n; i++) p = p.next;
		return p;
	}
	
	public static QueueNode mergeSort(QueueNode start, int length) {
		if (length > 1) {
			QueueNode left = start;
			QueueNode mid = nThNode(start, length / 2 - 1);
			QueueNode right = mid.next;
			mid.next = null;
			left = mergeSort(left, length / 2);
			right = mergeSort(right, length - (length / 2));
			start = merge (left, right, length);
		}
		return start;
	 }
	 
	 public static QueueNode merge(QueueNode left, QueueNode right, int length) {
		QueueNode newstart;
		QueueNode p;
		if (left.lessOrEqual(right)) {
			newstart = left;
			p = left;
			left = left.next;
	   	}
		else {
			newstart = right;
			p = right;
			right = right.next;
		}
	   	for (int i = 0; i < length-1; i++) {
			if (right == null || (left != null && left.lessOrEqual(right))) {
				p.next = left;
				p = left;
				left = left.next;
			}
			else {
				p.next = right;
				p = right;
				right = right.next;
			}    
		}
		return newstart;
	}

Python Implementierung

Ich finde die Python Implementierung unnötig kompliziert, mein Vorschlag wäre:

def mergesort(a):
    if len(a)<2:
        return a
    else:
        b = mergesort(a[:len(a)/2])
        c = mergesort(a[len(a)/2:])
        return merge(b,c)

def merge(a,b):
    c = []
    while len(a)>0 and len(b)>0:
        if a[0]<=b[0]:
            c.append(a.pop(0))
        else:
            c.append(b.pop(0))
    c.extend(a)
    c.extend(b)
    return c

Davon abgesehen finde ich auch die vielen Implementierungen unnötig, einmal Pseudocode würde reichen!

Mischen?

Inwiefern wird bei diesem Verfahren denn gemischt? Ich finde es irreführend, in diesem Zusammenhang von "Mischen" zu sprechen. --Daniel Mex 20:53, 20. Jul. 2007 (CEST)

Verschiedene Arten des Mergesort

Wir haben in der Vorlesung 3 verschiedene Arten kennen gelernt, die sich in der Zerlegung des Arrays unterscheiden:

• rekursives Mischen: Zerlege das Array in gleich große Abschnitte und sortiere sie, wobei der erste Schritt der Sortierung wiederrum das zerlegen in 2 gleich große Abschnitte ist.
• Direktes Mischen: Betrachte jedes Element als eine Teilliste von einem Element
• Natürliches Mischen: Suche erst möglichst "Fragmente" von sortierten Teillisten

Habe nichts dazu im Artikel gefunden, werde sie nach der Klausur mal einbinden. -Mifritscher 14:13, 9. Feb. 2008 (CET)

Auch:

• 2-Wege-Mergesort
• reines 2-Wege-Mergesort
• natürliches 2-Wege-Mergesort

--Kissaki 19:04, 12. Jul. 2008 (CEST)

trickreiche Implementierungen

Ich finde, in dem Satz Das Verfahren arbeitet bei Arrays in der Regel nicht in-place, es sind dafür aber (trickreiche) Implementierungen bekannt ist das trickreiche falsch gewählt. Lässt man das Wort weg, macht der Satz wenig Sinn, und das obwohl er in der Klammer steht. --Zhujik 18:15, 18. Jul. 2008 (CEST)

Englisch-Lexikon: merge = verschmelzen

Ich finde die Formulierung "Mischen" bei Mergesort unglücklich - Mischen bedeutet doch, etwas durcheinanderbringen, z.B. Spielkarten mischen. Genau das Gegenteil geschieht aber beim Merge-Schritt: Es entsteht eine sortierte Folge. Ich plädiere daher dafür, den Ausdruck "Verschmelzen" zu verwenden - im übrigen auch die korrekte Übersetzung von to merge. --91.6.231.157 06:47, 19. Jul. 2009 (CEST)

gudn tach!

mischen bedeuten nicht nur durcheinanderbringen, sondern u.a. auch vermischen, zusammenbringen, siehe duden. und gemaess pons-online bedeutet to merge insb. im zusammenhang mit computern eben mischen. leo fuehrt als uebersetzung von merge sort [tech.] den begriff mischsortieren, so wie ich ihn auch schon in der informatik (wenn auch selten, da meist der englische ausdruck verwendet wird) gelesen habe.

der begriff sollte deswegen erwaehnung finden. -- seth 23:14, 19. Jul. 2009 (CEST)

Veranschauungsgrafik

Ich habe Kritik an der Veranschauungsgrafik auszuüben: Datei Diskussion:Mergesort.png. --Jobu0101 13:41, 12. Nov. 2009 (CET)

(Ver)mischen vs. Verschmelzen

Ich denke wir sollten uns auf einen Begriff für den Gebrauch im Artikel beschränken und den anderen nur bei der ersten Nennung in Klammer anfügen. z.b. [...] Verschmelzen (auch Mischen) [... und dann nur noch ...] Verschmelzen Persönlich finde ich den Ausdruck Verschmelzen um einiges besser geeignet, da dieser nicht so irreführend ist wie der deutsche Ausdruckt Vermischen. Wir sortieren ja, mischen ist praktisch das umgekehrte. (Obwohl beie Übersetzungen für das enlgische merge korrekt wären) In der deutschen Literatur werden beide Begriffe verwendet, aber in einem Artikel / einem Buch allein, ist immer nur ein Artikel, sonst fehlt die Konstanz und Vereinheitlichung. Deshalb sollten wir das dringend anpassen. Welcher Begriff zu wählen ist kann ja genauer untersucht werden...

-- Dolan 02:11, 13. Mär. 2010 (CET)

Erstmal stimme ich Dir völlig zu in Bezug auf die einheitliche Verwendung nur eines Begriffes. Und ob eine Übersetzung passend ist oder nicht, kommt auf den Zusammenhang an. Nicht jeder Ausduck, der in einem Wörterbuch in einer Liste von Übersetzungsmöglichkeiten eines Begriffs genannt wird, ist in jedem Kontext richtig oder passend -- das sollte doch wohl klar sein. Auch wenn "mischen" nicht nur "durcheinanderbringen" bedeutet, sondern u.a. auch "vermischen, zusammenbringen", so ist das hier dennoch nicht der treffende Begriff. Ich werde die Milch, die ich gleich in meinen Kaffee schütte, mit diesem mischen, nämlich vermischen bzw. zusammenbringen. Dabei geht es um eine (möglichst) homogene Verteilung, ganz im Sinne von vermischen, innig miteinander verbinden. Es werden dabei aber weder Moleküle noch sonst irgendetwas sortiert. Tatsächlich hat die Ordnung gegenüber dem vorherigen Zustand (Milch und Kaffee in getrennten Behältnissen) abgenommen, während es der einzige Zweck des Sortierens ist, dass dadurch die Ordnung zunimmt. Fazit: "Mischen" ist hier als Übersetzung von "merge" völlig irreführend. (nicht signierter Beitrag von 87.123.107.254 (Diskussion) 15:41, 12. Aug. 2010 (CEST))

Der Autor des Algorithmus

Wenn der Algorithmus wurde von von Neumann im Jahre 1945 gebaut, wie im Artikel angegeben --- müssen einen Verweis auf veröffentlichte Arbeiten von von Neumann im Jahre 1945. Wenn der Algorithmus nur in den Quellen des Jahres 1998, wird der Algorithmus des gleichen Jahres, also 1998, nicht 1945 beschrieben. Ohne die ursprüngliche Bezugnahme jede Andeutung, dass jemand etwas erfunden, sind nur Gerüchte. Link ist unbedingt erforderlich!Riemann'sZeta 22:39, 12. Apr. 2011 (CEST)

Please keep the discussion in one place only. en:Talk:Merge sort. -- 213.85.69.114 23:11, 12. Apr. 2011 (CEST)

Es ist ziemlich plausibel, dass so etwas relativ simples wie MergeSort "nebenbei", gewissermaßen als Teil eines Proof-of-Concepts entsteht, wenn man dabei ist, einen realen programmgesteuerten Rechenautomaten und dessen ISA zu konstruieren. Natürlich wäre für den vorliegenden Artikel ein entsprechendes Dokument schön.

Vielleicht ist [2] (erwähnt in [3]) ein Orignal-Fragment, man weiß es nicht... Such' selbst oder schreib' Knuth 'ne E-Mail. Vielleicht hat er ja eine stichhaltige Rechtfertigung. :)

Und nochmal betont: Primärquellen sind nicht erforderlich. --Daniel5Ko 23:28, 12. Apr. 2011 (CEST)

Quicksort ist Mergesort überlegen

Was für ein Käse steht denn da? "Damit ist Mergesort hinsichtlich der Komplexität dem Quicksort gewissermaßen überlegen, da der Quicksort (ohne besondere Vorkehrungen) ein Worst-Case-Verhalten von ${\mathcal {O}}(n^{2})$ besitzt. Die Wahrscheinlichkeit, dass dieser Fall auftritt, ist jedoch so gering, dass Quicksort in der Praxis bessere Ergebnisse erzielt." Ich werde diese Formulierung ändern, damit klar wird, dass das nur im RAM gilt. --mafutrct (Diskussion) 18:00, 17. Mai 2014 (CEST)

Ich kann mit dieser Formulierung ebenfalls nichts anfangen. Allerdings halte ich all diese scheinbar praxisrelevanten Behauptungen, insbesondere in einem Abschnitt über die Laufzeitkomplexität, für fehl am Platze. Erwägungen wie "QS ist schneller als MS" wegen "sequenzieller Operationen", sind im Sinne der Komplexität nicht nachvollziehbar, da beide eine Average- und Best-Case-Komplexität von n*log(n) haben. Und auch das verwendete Medium (zB. RAM) hat erstmal nichts mit der Komplexität zu tun. Das sind alles implementationsspezifische Details.

Darum schmeiße ich diese Behauptungen erstmal aus dem Abschnitt raus. Außerdem stehen Quicksort-Vergleiche ja bereits im Abschnitt "Sonstiges".

Übrigens tritt der Worst-Case beim Quicksort in der Praxis doch öfters ein, als man denkt. Oft ist die Eingabeliste nicht zufällig verteilt, sondern es wurden in eine bereits sortierte Liste ein paar Werte eingefügt. Verwendet ein einfaches QS nun als Pivot-Element das erste oder letzte Element, so hat man (fast) den Worst-Case.--Plankton314 (Diskussion) 20:51, 18. Mai 2014 (CEST)

C++ Implementierung

Ich hab mal meine, nach bestem Wissen und Gewissen erstellte und getestete C++ Implementierung hinzugefügt. Bitte um Sichtigung und gegebenenfalls Eingliederung in den Artikel.

Funktionsweise

Ich bin über die Animation und das Beispiel ein wenig verwundert, weil ich die Funktionsweise von Mergesort ganz anders kenne. In der Form wie ich Mergesort kenne, ist die Anzahl der Listen zu Beginn identisch mit der Anzahl der zu sortierenden Elemente. Es werden dann immer zwei benachbarte Listen zu einer zusammengerechnet, bis am Ende nur noch eine Liste vorhanden ist.

Mergesort wie ich es kenne...

a|n|e|x|a|m|p|l|e
an|ex|am|lp|e
aenx|almp|e
aaelmnpx|e
aaeelmnpx

--31.17.34.192 15:49, 12. Jul. 2022 (CEST)