ABSTRACT
S ORTING IS one of the fundamental operations will we study in this course.
The need to sort data has been critical since the inception of computer science.
For example, bubble sort, one of the original sorting algorithms, was analyzed to
have average and worst case performance of O ( n2
) in 1956. Although we know that
comparison sorts theoretically cannot perform better than O ( n lg n
) in the best case,
better performance is often possible-although not guaranteed-on real-world data.
Because of this, new sorting algorithms continue to be proposed.
