All too often in an application, there’s a need to sort a list of items. In this article, I will cover some of the more common sorting algorithms and give a few tips on choosing the right one for the job. I will cover the classic “Bubble sort” and “Insertion sort,” right through to the difficult “Exchange sort” and “Stack sort.” Then, you will look into a “Hybrid sort” that is a mix of the “Insertion and Stack sort” algorithms. You also will look at the advantages and disadvantages of each sorting algorithm.
First, look at a list of different sorting algorithms with a short list of details. ‘Stable’ refers to the ability of the sort algorithm to keep identical items in the original order.
| Sort Name | Method | Stable? | Short Description |
|---|---|---|---|
| Bubble Sort | Exchanging | Yes | Basic two-loop sort |
| Cocktail Sort | Exchanging | Yes | Bi-directional Bubble sort |
| Comb Sort | Exchanging | No | Faster variation of the Bubble sort |
| Gnome Sort | Exchanging | Yes | Hybrid (Bubble and Insertion Sort) |
| Selection Sort | Selection | No | In-place comparison sort |
| Insertion Sort | Insertion | Yes | Simple comparison sort |
| Shell Sort | Insertion | No | Generalization of insertion sort |
| Binary tree sort | Insertion | Yes | Builds a Binary tree of the data and uses the tree to sort |
| Library Sort | Insertion | Yes | Insertion sort that leaves gaps in the list for subsequent elements |
| Merge Sort | Merging | Yes | A divide, sort, and merge algorithm |
| In-Place Merge Sort | Merging | Yes | Space-optimised version of the merge sort |
| Heap Sort | Selection | No | Two-stage comparison style sort |
| Smooth Sort | Selection | No | Small variation of a Heap sort |
| Quick Sort | Partitioning | No | Recursive partition and sort |
| Intro Sort | Hybrid | No | Hybrid of quick sort and heap sort |
| Patience Sorting | Insertion | No | Statistical ordering of elements |
| Stand Sort | Selection | Yes | Useful for data which is stored in a linked list |
There are still more sorting algorithms and methods, but some require specific hardware, like the “Bead sort” and “Network Sort,” and others are so impractical that they exist solely for demonstration purposes, like the “Bogo Sort” and “Stooge Sort” (named after the Three Stooges).
