A collection of sorting algorithms implemented in C++ to see the advantages and disadvantages of each one of them
A slow sorting algorithm for the simplest data sets
| Case | Performance |
|---|---|
| Worst case performance | O(n^2) |
| Best case performance | O(n) |
| Average case performance | O(n^2) |
| Auxiliary Space | O(1) |
Insertion sort is a simple sorting algorithm that works the way we sort playing cards. It is efficient for (quite) small data sets.
It is often used when the data set is nearly sorted (it takes minimum time (Order of n)).
It takes maximum time to sort if elements are sorted in reverse order.
| Case | Performance |
|---|---|
| Worst case performance | O(n^2) |
| Best case performance | O(n) |
| Average case performance | O(n^2) |
| Auxiliary Space | O(1) |
Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited
| Case | Performance |
|---|---|
| Worst case performance | O(n^2) |
| Best case performance | O(n^2) |
| Average case performance | O(n^2) |
| Auxiliary Space | O(1) |
Merge Sort is a Divide and Conquer algorithm that continually splits a list in half and then merge the sublists in a sorted way.
A single most important advantage of merge sort over quick sort is its stability: the elements compared equal retain their original order.
| Case | Performance |
|---|---|
| Worst case performance | O(n log n) |
| Best case performance | O(n log n) |
| Average case performance | O(n log n) |
| Auxiliary Space | O(n) |
Quick Sort is a recursive sorting algorithm that is more effective than other O(nlogn) algorithms for large datasets that fit in memory, but is unstable. Quick Sort in general does not requiere extra space while Merge Sort requires O(n) extra storage
| Case | Performance |
|---|---|
| Worst case performance | O(n^2) |
| Best case performance | O(n log n) |
| Average case performance | O(n log n) |
| Auxiliary Space | O(log(n)) |
