Schreibe eine Funktion sort(a), die das Array a an Ort und Stelle sortiert, oder geh von einer Vorlage aus. Sie läuft in deinem Browser, getrennt von der Seite und mit einem Limit von 8 Sekunden, mit Arrays von 8 bis 1024 Elementen, bereits sortiert, umgekehrt und zufällig. Dein Code muss dafür nicht angepasst werden: Jedes Mal, wenn du zwei Elemente mit <, > oder durch Subtraktion vergleichst, zählt das als ein Vergleich; jedes a[i] ist ein Lesezugriff und jedes a[i] = … ein Schreibzugriff.
Bei großen Größen testet das Tool, welche Kurve am besten zu deinen Zählungen passt: n, n log n oder n², und mit welcher Konstante («≈ 0,5·n²»). Das ist eine Messung, kein Beweis: Ein Algorithmus kann bei diesen Größen wie n log n aussehen und es doch nicht sein.
Eine Sortierung ist stabil, wenn zwei Elemente mit demselben Schlüssel in der Reihenfolge bleiben, in der sie ankamen. Die Tool prüft das mit einem Array voller wiederholter Schlüssel, die sich ihre ursprüngliche Position merken.
Vergleiche mit === (sie rufen valueOf nicht auf) und alles, was du in Hilfsarrays machst, außer wenn du zurück in a schreibst. Ein Element mit einer einzelnen Zahl zu vergleichen zählt als halber Vergleich.
Schreibe deine Sortierung (oder geh von einer Vorlage aus) und sieh, wie viel sie wirklich arbeitet: Vergleiche, Lese- und Schreibzugriffe, mit Arrays von 8 bis 1024 Elementen.