Most people are aware of the various Sorting Algorithms and even their respective time complexities, best case, worst case etc. However, they have little knowledge about the types of Sorting Algorithms. Knowing about these different types is important because it reveals important information regarding the workings of the Sorting Algorithm, as well as it’s limitations.
There are three main categories that we will be discussing. Recursive and Iterative, Stable and Non-Stable, and in-place and out-of-place.
Recursive and Iterative
Sorting Algorithms are either of recursive nature, or iterative.
Recursive: This is when a function calls itself within it’s body. Typically Recursion takes extra memory due to the stacking of recursive calls in the stack memory. However, (most) modern Compilers also have optimizations that automatically that can convert Recursive code, to iterative during compile time, which removes the extra memory issue. Recursive solutions are often popular due to their short and effective ways of sorting.
Iterative: Uses Regular loops to do the sorting. A fairly standard way of sorting.
Note: This is a pretty debated topic, with results varying significantly in various tests performed.
In-Place and Out-of-Place
In-place Sorting: Sorting that takes place without allocating any extra memory, typically within the same array/list. Typically done by swapping values around in the same array.
Out-of-place Sorting: Sorting Algorithms that need extra memory while sorting. They typically create a new array/list into which the output is sorted.
In general, In-place sorting algorithms are the preferred type due to the lower memory requirements. Sorting Algorithms with both Recursion and Out-of-place types, have the highest memory requirements.
Examples of Out-of-place Sorting Algorithms is Merge Sort, which creates a new “result” array into which the individual elements are sorted. Example of a In-place sorting Algorithm is Bubble Sort, which merely swaps two values after checking to see if they are in sorted order or not.
Stable and non-Stable Algorithms
Another important thing we keep in mind is whether a Sorting Algorithm in stable or not. This is not to be confused with the more common usage of stable, which implies consistency. Rather, it takes on a slightly different meaning when applied to sorting Algorithms.
Let us consider the following list of numbers. We’re going to give them index numbers so we can differentiate between the duplicate elements present there.
3 (0)
8 (1)
4 (2)
4 (3)
1 (4)Now, when we sort these numbers, we may end up with the following result.
1 (4)
3 (0)
4 (3)
4 (2)
8 (1)The key point here, is that the duplicate “4's” index positions have now been changed.
On the other hand, if the Algorithm being used was stable, we would end up with the following result.
1 (4)
3 (0)
4 (2)
4 (3)
8 (1)This may not be important for most use cases, but if a situation arises where the order of items while being sorted is important, you will have to use a stable sorting algorithm. This is typically important where we have data in a “key-pair” format, like the one above.
The “Classic” version of most Algorithms are unstable, but can be modified into stable variants.
If you want to learn more about the various Sorting Algorithms out there, you can check out our Introduction to Sorting Algorithms guide. Likewise, if you are interested in the comparisons between all the sorting algorithms, you can check out our Comparison of Sorting Algorithms guide.
You can also check out our YouTube series on Sorting Algorithms!
This marks the end of the Types of Sorting Algorithms tutorial. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.
