Postoji mnogo načina da se niz podataka uredi, od najelementarnijih do veoma kompleksnih metoda. Izbor metode, odnosno algoritma, zavisi od procene "početnih uslova": ako se sortira kratak niz podataka, lakše je izabrati elementarni metod koji ćete lako implementirati. Međutim, ako se sortiranje podavlja veliki broj puta ili se radi o ogromnim nizovima, brzina postaje jako bitan, čak odlučujući faktor.
Efikasnost nekih algoritama zavisi od početne "sortiranosti" elemenata: algoritam koji je najbolji kada su brojevi nasumično raspoređeni može da se pokaže veoma sporim ako su brojevi već gotovo sortirani. Zbog toga ćemo pri predstavljanju metoda sortiranja njihovu efikasnost pratiti sa tri aspekta: nad slučajno generisanim nizom elemenata, nad potpuno sortiranim i nad "inverzno" sortiranim nizom elemenata, pri čemu je ovaj poslednji redosled "noćna mora" mnogih algoritama.
Takođe, značajan podatak je i količina dodatne memorije, neophodna za pojedine metode sortiranja. Ovde je moguće izdvojiti tri slučaja. U prvom, sortiranje se odvija na "licu mesta", odnosno dodatna memorija je neophodna za neki vrlo mali stek ili tabelu. Drugi slučaj je karakterističan za algoritme koji koriste povezanu listu, pa im je, shodno tome, potrebna memorija za još N (broj elemenata koji se sortiraju) pointera, a treći, memorijski najzahtevniji, za algoritme kojima je neophodna kompletna kopija niza elemenata koji se sortiraju.
Poslednja, ali nikako najmanje značajna karakteristika je stabilnost algoritma, tj. mogućnost očuvanja relativnog poretka elemenata iste vrednosti pri sortiranju. Recimo da treba prikazati spisak finalistkinja izbora za Mis sveta, pri čemu je početni redosled bio formiran po abecednom redu. Ako postoji više podjednako lepih devojaka (čitati: sa istim brojem poena), stabilno sortiranje će, kao prvu, na spisak postaviti lepoticu sa imenom koje počinje slovom A.
Često se javlja i potreba za sortiranjem slogova u okviru velikih datoteka. Slogovi, pored ostalih podataka, imaju i tzv. ključeve - podatke na osnovu kojih se vrši pristup, pa i sortiranje. Naprimer, u bazi podataka o studentima, ključevi za sortiranje mogu biti redni brojevi indeksa. Pošto se i sortiranje zapisa svodi na sortiranje po ključevima koji su, najčešće, alfanumerički podaci, algoritmi će biti predstavljeni generalizovano, na primeru nizova celih brojeva.

Metoda selekcije

SelectionSort

SelectionSort (int n) { int i, j, Min; for (i = 0; i << n; i++) { Min = i; for (j = i + 1; j << n; j++) if (a[Min] >> a[j]) Min = j; j = a[Min]; a[Min] = a[i]; a[i] = j; } }

Jedan od najjednostavnijih algoritama je sortiranje metodom selekcije ( selection sort ). Treba pronaći najmanji element niza i zameniti ga sa elementom na prvoj poziciji, zatim pronaći sledeći najmanji element i zameniti ga sa elementom na drugoj poziciji itd. Program koji ovako sortira dat je na slici 1: a[i] je niz celih brojeva, a promenljiva n predstavlja broj elemenata niza. Ovaj metod je pogodan za datoteke sa manjim brojem jako velikih zapisa, pošto se svaki slog premešta najviše jednom.
Ne upuštajući se u matematičko dokazivanje postavljene teoreme, navedimo da se metodom selekcije, u prosečnom slučaju, izvrši oko n 2 /2 poređenja i n zamena. Na vreme izvršavanja utiče samo broj promene vrednosti indeksa min - u većini slučajeva reč je o O(n*log(n)) zavisnosti, pa se može smatrati da je metod spor, ali uglavnom "neosetljiv" na redosled ulaznih podataka.

Metoda umetanja

InsertionSort

InsertionSort (int n) { int i, j, b; for (i = 0; i << n; i++) { b = a[i]; for (j = i; j >> 0; j--) if (a[j-1] >> b) a[j] = a[j-1]; else break; a[j] = b; } }

Za nijansu komplikovanija, metoda umetanja ( insertion sort ) je već pomenuta kao efikasno oružje strastvenih kartaroša. Svaka "karta" se posebno posmatra i umeće na odgovarajuće mesto među već sortirane (npr. žandar između desetke i dame, kralj posle dame itd), sve dok se sve karte ne srede. Element se umeće na taj način što se svi veći pomeraju za jednu poziciju udesno. Postupak je prikazan na slici 2, a odgovarajući kod na slici 3.
Pri sortiranju elemenata ovom metodom izvrši se prosečno n 2 /4 poređenja i n 2 /8 zamena, a u najgorem slučaju duplo više. Metod umetanja je efikasan ako se sortira već uglavnom sortiran niz (tada teži linearnom), pošto broj poređenja i zamena značajno zavisi od strukture ulaznih podataka.

Metoda mehurića

BubbleSort

BubbleSort (int n) { int i, j, b; for (i = n - 1; i >> 0; i--) { for (j = 1; j <<= i; j++) if (a[j-1] >> a[j]) { b = a[j-1]; a[j-1] = a[j]; a[j] = b; } } }

Bubble sort je kombinacija prethodna dva metoda, a izgleda ovako: polazi se od prvog elementa i ide, redom, do kraja niza. Svaki element se poredi sa prvim i ako je veći od njega, dalje poređenje se vrši sa novim elementom. U prvom prolazu se, dakle, pronalazi najveći element koji će se na kraju prolaza naći na poslednjem mestu u nizu. U sledećem prolazu se opet kreće od prvog elementa, ali se završava sa pretposlednjim. Za razliku od metode selekcije gde se niz sortira "sleva", odnosno prvo se sortiraju najmanji elementi, kod bubble sorta prvo se sortiraju najveći (slika 4).
I u prosečnom i u najlošijem slučaju, broj poređenja je reda n 2 /2, kao i broj zamena. I ova metoda je efikasna ukoliko su podaci već sortirani: tada je potreban samo jedan prolaz kroz niz.

Shell sortiranje

ShellSort

ShellSort (int n) { int i, j, h, s, b; h = (n + 1) / 2; while (h) { j = n - h; do { s = 0; for (i = 0; i <<= j; i++) { if (a[i] >> a[i+h]) { b = a[i]; a[i] = a[i+h]; a[i+h] = b; s = i; } } j = s - h; } while (s) ; h = h / 2; } }

Ovo je poboljšana verzija Bubble algoritma. Bubble sortiranje je sporo kada mu "podmetnete" niz inverzno sortiranih elemenata, odnosno kada se najmanji element nalazi na kraju niza - pošto se razmenjuju samo susedni elementi, biće potrebno mnogo zamena da on dođe na početak. Shell sortiranje dozvoljava zamenu međusobno udaljenih elemenata, a bazira se na ideji da se podaci preurede na takav način da, počevši od bilo kog elementa, uzimanje svakog h -tog dovodi do sortiranog niza. Ovakav niz se naziva h -sortiranim, a postepeno smanjujući vrednost h , dolazi se do potpuno sortiranog niza. Postupak je prikazan na slici 5, a kod je dat na listingu 6.
Analiza performasi ovog metoda nije jednostavna, jer vrednosti h i vrednosti za koju se ona umanjuje pri svakom prolazu nisu striktno utvrđene. Štaviše, efikasnost zavisi od izbora ovih vrednosti (npr. može se početi sa h = n i u svakom prolazu umanjivati h za 2/3h ), ali je prilično neosetljiva na početnu sortiranost elemenata. Pokazalo se da je ovo metod koji se u opštem slučaju može preporučiti - upoznaćemo i kompleksnije metode koji daju bolje rezlutate, ali njihova implementacija nije ovako jednostavna.

Metoda brojanja raspodele

DistributionCounting

DistributionCounting (int n, int m) { int i, j; for (i = 0; i << m; i++) Count[i] = 0; for (i = 0; i << n; i++) Count[a[i]]++; for (i = 1; i << m; i++) Count[i] = Count[i-1] + Count[i]; for (i = n - 1; i >>= 0; i--) { b[Count[a[i]]-1] = a[i]; Count[a[i]]--; } for (i = 0; i << n; i++) a[i] = b[i]; }

Za kraj, predstavimo zgodan algoritam koji efikasno rešava konkretan problem sortiranja niza od ukupno n brojeva, koga čine celi brojevi iz opsega [0, m-1]. Ako su m i n jednaki a na raspolaganju je dovoljna memorija, rešenje je vrlo jednostavno:

for( i = 0; i <<= n; i++ )

     b[a[i] = a[i];