File:Merge-sort-example-300px.gif · Wikimedia Commons · See Wikimedia Commons
Key facts
- Class
- Sorting algorithm
- Data structure
- Array
- Worst case performance
- O ( n log n ) {\displaystyle O(n\log n)}
- Best case performance
- Ω ( n log n ) {\displaystyle \Omega (n\log n)} typical, Ω ( n ) {\displaystyle \Omega (n)} natural variant
- Average performance
- Θ ( n log n ) {\displaystyle \Theta (n\log n)}
- Worst case space complexity
- O ( n ) {\displaystyle O(n)} total with O ( n ) {\displaystyle O(n)} auxiliary, O ( 1 ) {\displaystyle O(1)} auxiliary with linked lists
via Wikipedia infobox
Wikidata facts
- Instance of
- divide-and-conquer algorithm
- Subclass of
- sorting algorithm
- Image
- Merge sort algorithm diagram.svg
Show 7 more facts
- discoverer or inventor
- John von Neumann
- Stack Exchange tag
- stackoverflow.com/tags/mergesort
- uses
- merge algorithm
- Commons category
- Merge sort
- derivative work
- Timsort
- time of discovery or invention
- 1945-00-00
- maintained by WikiProject
- WikiProject Mathematics
via Wikidata · CC0
Article · Italiano
Il merge sort è un algoritmo di ordinamento basato su confronti che utilizza un processo di risoluzione ricorsivo, sfruttando la tecnica del Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato da John von Neumann nel 1945. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.
Abstract from DBpedia / Wikipedia · CC BY-SA