9. Sorting Methods

The function of sorting or ordering a list of objects according to some linear order is so fundamental that it is ubiquitous in engineering applications in all disciplines. There are two broad categories of sorting methods: Internal sorting takes place in the main memory, where we can take advantage of the random access nature of the main memory; External sorting is necessary when the number and size of objects are prohibitive to be accommodated in the main memory.

The Problem:

• Given records r₁, r₂,..., r_n, with key values k₁, k₂,..., k_n, produce the records in the order 

                                                                            r_i1, r_i2,..., r_in,

such that 

                k_i1$$\leq$$k_i2$$\leq$$...$$\leq$$k_in
 

• The complexity of a sorting algorithm can be measured in terms of

*

number of algorithm steps to sort n records

*

number of comparisons between keys (appropriate when the keys are long character strings)

*

number of times records must be moved (appropriate when record size is large)

• Any sorting algorithm that uses comparisons of keys needs at least O(n log n) time to accomplish the sorting.

 

Sorting Methods
Internal	External
(In memory)	Appropriate for secondary storage
quick sort
heap sort	mergesort
bubble sort	radix sort
insertion sort	polyphase sort
selection sort
shell sort