SORTING ALGORITHMS

INTRO

A sorting algorithm is one that puts elements in a list into an order.
The most frequently used orders are:

• Numerical order
• Lexicographical order.

These can either be ascending or descending.

Efficient sorting is important for optimizing the efficiency of other algorithms such as search and merge algorithms that require data to be in sorted lists.
Sorting is also useful for canonicalizing data and for producing human-readable output.
In Computer Science, canonicalization is the process of converting data that has more than one possible representation into a standard/ normal form

Formally , the output of any sorting algorithm must satisfy two conditions.

• The output must be in monotonic order. i.e. each element is no smaller/ larger than the previous element, according to the required order.
• The output is a permutation of the input. i.e. it is a reordering yet retaining all of the original elements.
  For optimum efficiency, the input data should be stored in a data structure that allows random access rather than one that allows only sequential access.

CLASSIFICATION

Sorting algorithms can be classified by:

• Computational complexity. This classifies an algorithm based on its usage of resources. This gives 3 behaviors in terms of the size of the list

  • Best
  • Worst
  • Average case

• Memory usage

• Recursion
  Merge sort is both recursive and non recursive.

• Stability
  stable algorithms maintain the relative order of records with equal keys.

• Whether or not they are a comparison sort.

• Serial or Parallel

• Adaptability. This determines whether the presortedness of input affects its runing time.

-Online
online algorithms can sort a constant stream of input.

COMPARISON OF ALGORITHMS