Sorting

From

← Searching

↑ Contents: CS2

End

Sorting is one of the most studied areas 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( N² ) and which is best for small files, say 50 items or less. An advanced sort is one whose run time is O( N log² N ) and which is best for large files.

The Sorting Problem

Given a set of records r₁, r₂, …, r_n with keys k₁, k₂, …, k_n respectively, arrange the records in an order S = <s₁, s₂, …, s_n> such that records r_s1 , r_s2 , ..., r_sn have keys obeying the property k_s1 ≤ k_s2 ≤ ... ≤ k_sn, called ascending order or k_s1 ≥ k_s2 ≥ ... ≥ k_sn, 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.

• Simple Sorts
• Advanced Sorts
• Non-comparision Sorting
• External Sorting

---

---