Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

The most frequently used orders are numerical order and lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product).
Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

More formally, the output of any sorting algorithm must satisfy two conditions:

1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
2. The output is a permutation (a reordering, yet retaining all of the original elements) of the input.

Example #1: Let's take a list of characters which are sorted in increasing order of their ASCII values. That is, the character with lesser ASCII value will be placed first than the character with higher ASCII value

C O D E B O U N T I F U L -------> B C D E F I L N O O T U U

(Input)                                           (Output)

Example #2: Now let's take a list of integers which are sorted in decreasing order of their ASCII values.

8 2 0 7 5 4 9 1 6 3     ------->     9 8 7 6 5 4 3 2 1 0

(Input)                                      (Output)

Here is a list of well-known sorting algorithms:

• Selection Sort
• Bubble Sort
• Recursive Bubble Sort
• Insertion Sort
• Recursive Insertion Sort
• Merge Sort
• Iterative Merge Sort
• Quick Sort
• Iterative Quick Sort
• Heap Sort
• Counting Sort
• Radix Sort
• Bucket Sort
• ShellSort
• TimSort
• Comb Sort
• Pigeonhole Sort
• Cycle Sort
• Cocktail Sort
• Strand Sort
• Bitonic Sort
• Pancake sorting
• Binary Insertion Sort
• BogoSort or Permutation Sort
• Gnome Sort
• Sleep Sort – The King of Laziness / Sorting while Sleeping
• Structure Sorting (By Multiple Rules) in C++
• Stooge Sort
• Tag Sort (To get both sorted and original)
• Tree Sort
• Cartesian Tree Sorting
• Odd-Even Sort / Brick Sort
• QuickSort on Singly Linked List
• QuickSort on Doubly Linked List
• 3-Way QuickSort (Dutch National Flag)
• Merge Sort for Linked Lists
• Merge Sort for Doubly Linked List
• 3-way Merge Sort

Sorting algorithms are often classified by:

Computational complexity (worst, average and best behavior) in terms of the size of the list (n). For typical serial sorting algorithms good behavior is O(n log n), with parallel sort in O(log2 n), and bad behavior is O(n2). (See Big O notation.) Ideal behavior for a serial sort is O(n), but this is not possible in the average case. Optimal parallel sorting is O(log n). Comparison-based sorting algorithms need at least Ω(n log n) comparisons for most inputs.
Computational complexity of swaps (for "in-place" algorithms).
Memory usage (and use of other computer resources): In particular, some sorting algorithms are "in-place". Strictly, an in-place sort needs only O(1) memory beyond the items being sorted; sometimes O(log(n)) additional memory is considered "in-place".
Recursion: Some algorithms are either recursive or non-recursive, while others may be both (e.g., merge sort).
Stability: stable sorting algorithms maintain the relative order of records with equal keys (i.e., values).
Whether or not they are a comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator.
General method: insertion, exchange, selection, merging, etc. Exchange sorts include bubble sort and quicksort. Selection sorts include shaker sort and heapsort.
Whether the algorithm is serial or parallel. The remainder of this discussion almost exclusively concentrates upon serial algorithms and assumes serial operation.
Adaptability: Whether or not the presortedness of the input affects the running time. Algorithms that take this into account are known to be adaptive.


We will discuss each sorting algorithm in upcoming posts.
Thanks for reading.