Merge sort

Průběh cvičení

Zopakovali jsme si myšlenku algoritmu merge sort. Řekli si, co, jak a proč dělá merge, a ukázali si příklad. Stručně jsme prošli jeho složitost (časovou i paměťovou).

Poznámky

Při implememtaci v C může u Microsoft kompilátoru být problém se statickou alokací pole s velikostí dle hodnoty proměnné (v Merge). Bez újmy na obecnosti můžete tyto alokace udělat pro původní velikost pole (konstanta).

Úkoly

1. Implementujte merge sort v jazyce C/Pythonu.
2. Na slidech prof. Bělohlávka (část 2, slide 86) máte k zamyšlení kombinaci merge sortu a insert sortu. Implementujte tuto myšlenku v C/Pytohnu.