There are many fundamental and advanced sorting algorithms. All sorting algorithms are problem-specific, which means they work well on some specific problem but do not work well for all the problems.
All sorting algorithms apply to specific kinds of problems. Some sorting algorithms apply to a small number of elements, some are suitable for floating point numbers, some are fit for specific range, some are used for large numbers of data, and some are used if the list has repeated values.
We sort data either in numerical order or lexicographical order, sorting numerical values either in increasing order or decreasing order and alphabetical values like addressee keys.
Classifying Sorting Algorithms :
We can classify sorting based on data size, based on information about data (comparison-based sorting, non-comparison-based sorting).
We can also classify the sorting algorithm based on other criteria: computational complexity, stability, memory usage, recursion, and comparison-based.
Choosing a Sorting Algorithm in Practice :
These questions may arise before choosing a sorting algorithm:
- Is the input size large or small?
- Are each item itself large or small?
- Is the item size fixed?
- In-memory sorting or external file sorting?
- Sorting only just indices, or must you move data ?
- Is stability a requirement ?
| S.No. | Problem Definition | Sorting Algorithms |
|---|---|---|
| 1. | The data to be sorted is small enough to fit into a processor‟s main memory and can be randomly accessed i.e. no extra space is required to sort the records (Internal Sorting). |
Insertion Sort, Selection Sort, Bubble Sort |
| 2. | Source data and final result are both sorted in hard disks (too large to fit into main memory), data is brought into memory for processing a portion at a time and can be accessed sequentially only (External Sorting). |
Merge Sort (business application, database application) |
| 3. | The input elements are uniformly distributed within the range [0, 1). |
Bucket Sort |
| 4. | Constant alphabet (ordered alphabet of constant size, multi set of characters can be stored in linear time), sort records that are of multiple fields. |
Radix Sort |
| 5. | The input elements are small. | Insertion Sort |
| 6. | The input elements are too large. | Merge Sort, Shell Sort, Quick Sort, Heap Sort |
| 7. | The data available in the input list are repeated more times i.e. occurring of one value more times in the list. |
Counting Sort |
| 8. | The input elements are sorted according to address (Address Computation). |
Proxmap Sort, Bucket Sort |
| 9. | The input elements are repeated in the list and sorted the list in order to maintain the relative order of record with equal keys. |
Bubble Sort, Merge Sort, Insertion Sort, counting sort |
| 10. | The input elements are repeated in the list and sorted the list so that their relative orders are not maintain with equal keys. |
Quick Sort, Heap Sort, Selection Sort, Shell Sort |
| 11. | A sequence of values, a0, a1… an-1, such that there exists an i, 0 ≤ i ≤ n −1, a0 to ai is monotonically increasing and ai to an-1 is monotonically decreasing. (sorting network) |
Biotonic -merge Sort |
| 12. | Adaptive sorting algorithms that are comparison based and do not put any restriction on the type of keys, uses data structure like linked list, stack, queue. |
Stack sort , deqsort, minmax sort |
Reference – Selection of Best Sorting Algorithm for a Particular Problem
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.