Sorting

From

---

Revision as of 14:48, 24 March 2009

Sorting is one of the most studied area of Computer Science. There are literally dozens of sorting algorithms. Sorting algorithms are divided along two dimensions: One dimension is simple sorts vs. advanced sorts. The other dimension is internal sorts vs. external sorts.

Internal sorts are sorting routines where the entire data to be sorted can be stored in the memory. An external sort is one where only part of the data to be sorted can fit into the memory.

A simple sort is characterized as one whose run time is O( N2 ) and which is best for small files, say 50 items or less. An advanced sort is one whose run time is O( N log2 N ) and which is best for large files.

The Sorting Problem

Given a set of records r1, r2, …, rn with keys k1, k2, …, kn respectively, arrange the records in an order S = <s1, s2, …, sn> such that records s1 s2 sn r , r , ..., r have keys obeying the property s1 s2 sn k ≤ k ≤ ... ≤ k , called ascending order or s1 s2 sn k ≥ k ≥ ... ≥ k , called descending order. Note that the sorting problem allows for duplicate keys.

A sorting algorithm is defined to be stable if the relative ordering between records with duplicate keys is maintained in the final ordering.