Flettesortering

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk
Flettesortering

Flettesortering (engelsk: merge sort) er en effektiv sammenligningsbasert sorteringsalgoritme. De fleste implementasjoner produserer en stabil sortering, noe som betyr at implementasjonen bevarer innmatningens rekkefølge av like elementer i den sorterte utmatningen. Flettesortering er en splitt og hersk-algoritme som ble oppfunnet av John von Neumann i 1945.[1] En detaljert beskrivelse og analyse av flettesortering ble gjort i en rapport av Neumann og Hermann Goldstine i 1948.[2]

Referanser[rediger | rediger kilde]

  1. ^ Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
  2. ^ Jyrki Katajainen, Jesper Larsson Träff: A meticulous analysis of mergesort programs, 1997