Obeleži sve kategorije koje odgovaraju problemu

Sortiranje je jedna od najdublje istraženih grana algoritama. Jedna cela knjiga u Knuth-ovoj seriji knjiga (~800 stranica) je posvećena sortiranju i pretraživanju. Sortiranje ima široku primenu. Ono omogućava brzo nalaženje traženog elementa u nizu. Podsetimo se da traženje elementa u nizu samo prolaženjem kroz sve elemente zahteva O(n) operacija, gde je n broj elemenata u nizu. Ukoliko je niz sortiran, nalaženje elementa korišćenjem binarne pretrage zahteva samo O(log n) operacija. Dva sortirana niza se mogu brzo spojiti u jedan sortirani niz koji sadrži elemente oba niza. Takođe, nalaženje duplikata u nizu se može lako uraditi sortiranjem, jer posle sortiranja duplikati se nalaze jedan pored drugog. Ovo su samo neke od mnogobrojnih primena sortiranja.

U praksi, nama je dat niz objekata koji imaju mnogo atributa i od tih atributa je izdvojen bar jedan po kojem treba da sortiramo. Međutim, mi ćemo se ovde ograničiti na sortiranje niza brojeva, pošto je prilikom sortiranja važan samo metod.

U lekciji Osnovni algoritmi sortiranja smo se upoznali sa nekim algoritmima koji zahtevaju O(n^2) operacija upoređivanja, a ovde ćemo se upoznati sa naprednijim algoritmima koji postižu donju granicu za sortiranje od O(n log n) upoređivanja. Takođe ćemo videti da ukoliko znamo neke osobine brojeva koje sortiramo, možemo sortirati u vremenskoj složenosti bržoj od O(n log n), tako sto ćemo zaobići operacije upoređivanja.