Sorting Algorithms

Internal

• Data Structures and Algorithms

Overview

Many programs use sorting as an intermediate step, and that is why sorting is considered a fundamental operation in computer science.

The sorting problem if formally defined as follows: given a sequence of n numbers (a₁, a₂, ... a_n) provided as input, the algorithm must produce as output a permutation (reordering) (a^'₁, a^'₂, ... a^'_n) of the input sequence such that a^'₁ ≤ a^'₂ ≤ ... ≤ a^'_n. A specific input sequence is called an instance of the sorting problem. Although conceptually we are sorting a sequence, the input comes to the sorting function as an array with n elements.

The numbers we wish to sort are also known as keys.

Comparison sort. Cannot do better than n lg n. Proof in a separate article.

Non-comparison sort.

Sorting algorithms characteristics:

• in-place
• stability

Sorting Algorithms

• Insertion sort
• Merge sort