This is a collection of the most popular sorting algorithms. I will frequently update this page with links for the description and their implementation in C.
It is an algorithm which arranges items in the list in certain order. These algorithms are important for optimizing the implementation of other algorithms (like search and merge algorithms) which requires input data to be in sorted lists.
We define the sorting problem like this..
Input : Sequence of N numbers ( i1, i2, i3, i4, …., iN)
Output: Sequence of N numbers ( j1, j2, j3, j4, …., jN) with the condition that ( j1 ≤ j2 ≤ j3 ≤ j4 …..≤ jN)
Sorting algorithms are often classified based on the difficulties that can happen in real life while implementing them. Problems that are considered frequently..
Worst, Average and Best case performance of the algorithm (usually run time) in terms of the size of list (N). For typical sorting algorithm best performance is O(N log N) and worst performance O(N²).
Memory Usage (and use of other computer resources)
Some sorting algorithms are ‘in place‘ (algorithms which overwrites its input with its output as it executes). Strictly, in place sort requires only O(1) memory. Some algorithms require O(N), O(log N) memory.
Another problem is the stability of the algorithm. A sorting algorithm is said to be stable if two objects with same element ( key ) appears in the same order in sorted output as they appear in the unsorted input array. Example clarifies the sentence..
Question : Sort words by first letter
Input : Bag Apple Ball
Output : Apple Bag Ball (stable)
Output : Apple Ball Bag (not stable)
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Further, sorting algorithms are classified based on whether or not they are comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator.
Comparison-based Sorting Algorithms
As said, comparison-based sorting algorithms find the relationship (less than or greater than or equal) between two objects by comparing them with each other. Main concern of these algorithms is to decrease the number of comparisons (lesser the comparisons, more effective is the algorithm). Let’s start with the naive ones and move on to the most sophisticated algorithms.
No. Algorithm : O(Best — Average — Worst) — O(Worst case memory)
1. Bubble sort : O(N — N² — N²) — O(1)
2. Selection sort : O(N² — N² — N²) — O(1)
3. Insertion sort : O(N — N² — N²) — O(1)
4. Merge sort : O(N log N — N log N — N log N) — O(N)
5. Heapsort : O(N log N — N log N — N log N) — O(1)
6. Quicksort : O(N log N — N log N — N²) — O(log N or N)
7. Timsort : O(N — N log N — N log N) — O(N)
Usage in practice
Most would say each algorithm has its trade-offs. Typically, default sort implementation for most of the languages is either Mergesort or Quicksort. As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses Timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE 7, on the Android platform, and in GNU Octave.