Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This is the complete cheatsheet for all the important sorting algorithms that comprises that will act as a summary of each concepts including time complexity, key weakness and strengths.
Table of contents:
- Comparison Based Sorting
- Non-comparison Based Sorting
- Hybrid Sorting
Comparison Based Sorting
Comparison-based sorting is a method of sorting elements in an array or list by repeatedly comparing pairs of elements and swapping them if they are not in the correct order.
It uses comparison operations to determine the relative order of elements. Examples of comparison-based sorting algorithms include bubble sort, insertion sort, selection sort, merge sort, and quick sort.
These algorithms are considered to be the most general and versatile type of sorting algorithm, as they can be applied to any type of data and can sort elements in ascending or descending order.
| Sorting-Algorithm | Best Time-Complexity | Average Time-Complexity | Worst Time-Complexity | Sapce-Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Merge Sort | O(n logn) | O(n log n) | O(n log n) | O(n) | step 1: divide the array into two halves step 2: sort each half recursively and then merge the two sorted halves back together | When the dataset to be sorted is large (also useful in Linked List sorting). When we need a faster algorithm (time is a major constraint). When memory overhead is not a big issue. |
| Quicksort | O(n logn) | O(n log n) | O(n^2) | O(1) | step 1: choose a "pivot" element from the array step 2: partition the array such that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side, then recursively apply the partitioning process to the resulting sub-arrays. | When we need a faster sorting algorithm with good locality of reference. When Internal sorting method is preferred. When extra memory is a constraint. When the dataset size is not very big. |
| Bubble Sort | O(n logn) | O(n log n) | O(n^2) | O(1) | step 1: repeatedly iterate through the array and compare adjacent elements, swapping them if they are in the wrong order step 2: continue iterating until no more swaps are needed | When a very simple and easy to implement sorting algorithm is desired. When we need stable sorting (maintaining relative order) is desired. When array size is relatively small. |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
Step 1: Iterate through the array starting from the first element. On each iteration, find the smallest (or largest) element from the remaining unsorted portion of the array.
Step 2: Swap the found element with the first element in the unsorted portion of the array. Step 3: Repeat step 1 and 2 for the remaining unsorted portion of the array. |
When the memory writing is an expensive operation. When there is constraint on memory usage. When the array size is relatively small. |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
step 1: start with an empty "sorted" portion of the array and iterate through the rest of the array, inserting each element into its proper position in the sorted portion
step 2: continue iterating until the entire array is sorted
Step 3: Repeat step 1 and 2 for the remaining unsorted portion of the array. |
When data is already sorted (or nearly sorted). When space efficiency is preferred over time. When stable sorting is required (relative order is important). When the dataset to be operated is of small size. |
| Cycle Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
Step 1: Iterate through the array starting from the first element. On each iteration, find the smallest (or largest) element from the remaining unsorted portion of the array.
Step 2: Swap the found element with the first element in the unsorted portion of the array. Also, keep track of the number of writes done in the array. |
Suitable for situations where memory is limited, and the cost of allocating and deallocating memory is high. |
| Heap Sort | O(n logn) | O(n logn) | O(n logn) | O(1) | Step 1: Create a heap from the input array. In a max-heap, the value of each parent node is greater than or equal to its children, while in a min-heap, the value of each parent node is less than or equal to its children. Step 2: Repeat the following process for the entire array: a) Swap the first element of the heap (which is the largest/smallest element) with the last element of the heap. b) Reduce the size of the heap by one and maintain the heap property by rearranging the elements. c) Repeat the process until the heap is of size 1. | When we need extreme elements very fast. When we need a partially sorted array. When we need to avoid quicksort worst case. |
| Shell Sort | Ω(n logn) | Θ(n^2) | O(n log(n)^2) | O(1) |
Step 1: Divide the input array into a set of smaller sub-arrays, called "gaps," using a gap sequence, such as the Knuth sequence. The gap sequence is chosen to reduce the amount of movement required to sort the elements.
Step 2: Sort each gap sub-array using an insertion sort algorithm. The elements within each gap sub-array are compared and swapped as necessary to sort the sub-array. |
The input data is a mix of numbers and strings, and it's not appropriate to use radix sort for sorting strings. |
Non-comparison Based Sorting
Non-comparison based sorting algorithms are sorting algorithms that do not rely on comparing the values of elements to determine their relative order.
They use other properties of the elements, such as their individual digits or their position in the input array, to sort the elements.
Examples of non-comparison based sorting algorithms include counting sort, bucket sort and radix sort.
These algorithms are efficient for sorting large numbers of integers or strings with a fixed length and have the advantage of being faster than comparison-based algorithms for large data sets.
However, they are not as versatile as comparison-based algorithms and may not be suitable for all types of data.
| Sorting-Algorithm | Best Time-Complexity | Average Time-Complexity | Worst Time-Complexity | Sapce-Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Radix Sort | Ω(n k) | Θ(n k) | O(n k) | O(n+k) |
Step 1: Using counting sort as a subroutine, sort the elements based on their least significant digit (or letter). This step is repeated for each digit (or letter) from the least significant digit to the most significant digit.
Step 2: After all digits (or letters) have been considered, the elements will be sorted in the desired order. |
When the biggest integer is shorter than array size. When we have fixed range of integers. When numbers are not much repeated but their length have same range. |
| Counting Sort | Ω(n +k) | θ(n +k) | O(n +k) | O(k) | Step 1: Create a counting array. Step 2: Iterate through the input array, incrementing the count of the corresponding element in the counting array. Iterate through the input array and place each element in its correct position in the output array based on the prefix sum array. | When the difference between various keys are not very big. When a very fast sorting algorithm is need (linear running time). When overhead space is not an big issue. |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(1) | Step 1: Distribute the elements of the input array into a number of "buckets" based on their value. Step 2: Sort the elements in each bucket using a different algorithm, such as insertion sort. After all the elements are sorted in their respective bucket, concatenate all the buckets in order. | When the range is much distributed and instead of limited range we have discrete elements . When faster implementation is not the top most priority. When space overhead is an issue. |
Hybrid Sorting
Hybrid sorting is a technique that combines two or more sorting algorithms to take advantage of the strengths of each one while minimizing their weaknesses.
The idea is to use a primary sorting algorithm that is efficient for the majority of the input data, and then use a secondary sorting algorithm to sort the remaining data that the primary algorithm is not efficient at sorting.
An example of this is Introsort, which combines quicksort, heapsort and insertion sort, and Timsort, which combines Insertion sort and Merge sort. Hybrid sorting has the advantage of being efficient for a wide range of input data and can be faster than a single sorting algorithm in some cases.
| Sorting-Algorithm | Best Time-Complexity | Average Time-Complexity | Worst Time-Complexity | Sapce-Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Tim Sort Algorithm | Ω(n) | Θ(n logn) | O(n logn) | O(n) |
Step 1: Run Insertion sort on small chunks of the input data. Timsort divides the input data into small partitions, and runs Insertion sort on each partition to sort the elements within that partition.
Step 2: Merge the sorted partitions: Timsort repeatedly merges the sorted partitions until the whole input data is sorted. |
well suited for sorting large data sets in memory, sorting data in a distributed environment, and sorting data in a parallel environment. |
| Intro Sort Algorithm | Ω(n logn) | θ(nlogn) | O(n logn) | O(logn) | Step 1: Run Quicksort on the input data. Step 2: Switch to Heapsort or Insertion sort. If the Quicksort algorithm encounters a situation where it is not making good progress (e.g the recursion depth becomes too large), it switches to Heapsort to sort the remaining data. Finally, if the recursion depth becomes too large again, it switches to Insertion sort. | When the difference between various keys are not very big. When a very fast sorting algorithm is need (linear running time). When overhead space is not an big issue. |
| Merge-insertion Sort Algorithm | O(N+Nlog(N/K) | O(N+Nlog(N/K) | O(NK + Nlog(N/K)) | O(1) |
Step 1: Run Insertion sort on small chunks of the input data. Run Insertion sort on each partition to sort the elements.
Step 2: Merge the sorted partitions: Merge-Insertion sort repeatedly merges the sorted partitions using the merge sort algorithm until the whole input data is sorted. |
well suited for sorting large data sets in memory, sorting data in a distributed environment, and sorting data in a parallel environment. |
