@Gajedi: Notations (sigma, O, theta)  and cases (worst, average, best) are different things.

http://lcm.csa.iisc.ernet.in/dsa/node9.html

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

@wai wai: I think the sorting you wanna do is Bucket sort. Though I am not very familiar with that one!