Mestimissortimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
navmall lehe lõppu |
link O-notatsiooni seletusele |
||
1. rida:
[[Pilt:Merge sort animation.gif|thumb|Mestimissortimist demonstreeriv animatsioon.]]
'''Mestimissortimine''' (''merge sort'') on [[Algoritmiline keerukus|O]](''n'' log ''n'') [[sortimisalgoritm]], leiutatud 1945 [[John von Neumann]]i poolt.<ref>[http://mathworld.wolfram.com/MergeSort.html Merge Sort – Wolfram MathWorld]</ref>
Mestimissortimine kasutab ära asjaolu, et kahe juba sorteeritud loendi ühendamine üheks sorteeritud loendiks on lihtne (lineaarse keerukusega). Algoritm jagab loendi kaheks enam-vähem võrdse suurusega loendiks, mis sorteeritakse omakorda mestimissortimisega, seejärel ühendatakse saadud sorteeritud loendid.
| |||