Sorting Algorithms and Analysis

Sorting -- Arranging items in some particular fashion mostly in some numerical or alphabetical order. Sorting can be classified on these basis.
Computational Complexity
Memory Usage
Stabiliy
Comparision - Non comparision sort.
First of all let me define some terms related to sorting that comes often when we define it.
External sorting -- When data being sorted doesnt fit into the main memory of a computing device(usually RAM) and a slower kind of memory(usually a hard drive) needs to be used.Suppose we have 10 MB of RAM and data is 12 MB to be sorted then in this case external sort is used. Merge sort is one example of external sort as a core.
Inplace sorting - It requires very little additional space besides the initial array holding the elements that are to be sorted. For sorting N elements, O(logn) extra space is required.This is reasonable because in a purely mathematical analysis of the algorithms, any sorting algorithm that operates on a contiguous array requires O(log n) extra space, since this is the number of bite required to represent an index into the array.
Stable -If the order of similar objects are maintained as in the given input after sorting.


reference: wikipedia

List of sorting algorithms
In this table, n is the number of records to be sorted and k is the number of distinct keys. The columns "Best", "Average", and "Worst" give the time complexity in each case; estimates that do not use k assume k to be constant. "Memory" denotes the amount of auxiliary storage needed beyond that used by the list itself.
These are all comparison sorts.
Name Best Average Worst Memory Stable Method Notes
Bubble sort O(n) — O(n2) O(1) Yes Exchanging Times are for best variant
Cocktail sort O(n) — O(n2) O(1) Yes Exchanging
Comb sort O(n log n) — O(n log n) O(1) No Exchanging
Gnome sort O(n) — O(n2) O(1) Yes Exchanging
Selection sort O(n2) O(n2) O(n2) O(1) No Selection
Insertion sort O(n) — O(n2) O(1) Yes Insertion
Shell sort O(nlog(n)) — O(nlog2(n)) O(1) No Insertion Times are for best variant
Binary tree O(nlog(n)) — O(nlog(n)) O(1) Yes Insertion
Library sort O(n) O(nlog(n))O(n2) O(n) Yes Insertion
Merge sort O(nlog(n)) — O(nlog(n)) O(n) Yes Merging
In-place merge O(nlog(n)) — O(nlog(n)) O(1) Yes Merging Times are for best variant
Heapsort O(nlog(n)) — O(nlog(n)) O(1) No Selection
Smoothsort O(n) — O(nlog(n)) O(1) No Selection
Quicksort O(nlog(n)) O(nlog(n)) O(n2) O(log n) No Partitioning Naive variants use O(n) space
Introsort O(nlog(n)) O(nlog(n)) O(nlog(n)) O(logn) No Hybrid
Patience sorting O(n) — O(nlog(n)) O(n) No Insertion Finds all the longest increasing subsequences within O(n log log(n))

This table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlog(n)) lower bound.
Name Best Average Worst Memory Stable
Pigeonhole sort O(n+k) — O(n+k) O(k) Yes
Bucket sort O(n) O(n) O(n2) O(k) Yes
Counting sort O(n+k) — O(n+k) O(n+k) Yes
Radix sort O(nk) — O(nk) O(n) Yes

This table describes some sorting algorithms that are impractical for real-life use due to extremely poor performance or a requirement for specialized hardware.
Name Best Average Worst Memory Stable Cmp Other notes
Bogosort O(n) O(n × n!)unboundedO(1) No Yes
Stooge sort O(n2.71)— O(n2.71) O(1) No Yes
Bead sort O(n) — O(n) — N/A No Requires specialized hardware
Pancake sorting O(n) — O(n) — No Yes Requires specialized hardware
Sorting networksO(log n)— O(log n) — Yes Yes Requires a custom circuit of size O(nlogn)

To be continued...