Mergesort

Från Unix.se, den fria unixresursen.

Mergesort är en sorteringsalgoritm för jämförelsebaserad sortering som bygger på algoritmkonstruktionsmönstret dekomposition.

Algoritmen

• Dela upp listan som ska sorteras i två dellistor.
• Se till att dellistorna var för sig är sorterade (t ex med rekursion).
• Så länge det finns element kvar i någon av dellistorna:
  • ta det "minsta" värdet av de som ligger först och lägg det i resultatlistan.

Mergesort är effektiv på stora listor, men inte så effektiv på små, så ofta används en annan algoritm för dellistorna när de har blivit tillräckligt små.

Analys

Loopen på slutet tar tid <math>\mathbf{O}(n)</math>, där n är antalet element som sorteras. På ett visst rekursionsdjup är antalet element uppdelat i ett antal delar, <math>m</math>, men varje del måste sorteras, dvs <math>m \mathbf{O}(n / m) = O(n)</math>. Rekursionsdjupet blir <math>\mathbf{O}(\log n)</math>, så den totala sorteringstiden blir <math>\mathbf{O}(n \log n)</math>.