Flettesortering
Flettesortering[1][2] (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.[3] En detaljert beskrivelse og analyse av flettesortering ble gjort i en rapport av Neumann og Hermann Goldstine i 1948.[4]
Se også[rediger | rediger kilde]
Referanser[rediger | rediger kilde]
- ^ «Algoritmer og datastrukturer - Kapittel 1 – ». www.cs.hioa.no. Besøkt 3. mars 2023.
- ^ Drange, Pål Grønås (27. januar 2023). «sorteringsalgoritme». Store norske leksikon (norsk). Besøkt 3. mars 2023.
- ^ 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.
- ^ Jyrki Katajainen, Jesper Larsson Träff: A meticulous analysis of mergesort programs, 1997