17.1.6. Best Sorting Algorithm?

Let us look back on all the different sorting algorithms that we have considered. One of the important criteria that we should not forget is that sorting often happens in phases. So, we might have a list of names of people say Aswin, Bharathi, Chander, and Deepa. So, we have sorted this in order and they might have got some marks in an exam. So, they may be got 60, 43, 60, and 95, now we might want to sort this by marks. So, when we sort this by marks of course, we need to exchange the position of Bharathi and Ashwin, but we do not want to exchange the position of Aswini and Chander. In other words, we do not want to disturb the sorting of alphabetical orders. So, the final answer should be Bharathi has 43, Ashwin has 60, Chander has 60 and Deepa has 95.

Sorting often occurs in stages or phases where an initial sorting criterion may be altered based on new data. In the example, names are first sorted alphabetically, and later by exam scores. This means that when re-sorting by scores, we want to maintain the alphabetical order for those with equal scores. Thus, even if Bharathi moves ahead of Ashwin due to a lower score, Ashwin and Chander should not switch positions as they have the same score. Maintaining the relative order of equal elements is crucial in sorting.

Imagine organizing books on a shelf. First, you arrange them alphabetically by title. Later, if you need to sort them by height for display purposes, you want to keep the alphabetical arrangement among books of the same height. So, if two books are of the same height but differ in title, their original alphabetical order remains intact even after the height sorting.

So, quick sort as shown is not a stable operation, so remember that we took that at a bit and in the at least in our implementation what we did was we constructed this lower set and then the upper set to the right of it. The crucial point is that we do this swap. Imagine that we have a situation where here we had for example, this point Ashwin with the 60 marks and Chander with also with 60 marks. So, at the point of constructing the lower set, they were in the correct order as in the original input. But, now after swapping what happens is that the pivot has come here and Chander with 60 marks has gone here. This swapping operation has basically reversed the order of A and C with this original input order.

Stable sorting algorithms maintain the relative order of equal elements after sorting, while unstable sorting algorithms do not guarantee this. Quick sort, as illustrated, is an unstable sorting algorithm because it can swap elements which alters their original order. For example, when two elements, Ashwin and Chander both scoring '60', are rearranged due to swapping during the partitioning step, their alphabetical order is disrupted. Hence, understanding whether a sorting algorithm is stable or unstable is crucial based on the requirements of the task.

Think of a race where several runners finish at the same time. If a stable sorting system is used, runners with the same finish time would keep the order they started in, maintaining positions to represent their original entry in the head-to-head rankings. Conversely, an unstable system might randomly change their finishing order, leading to confusion about who ranked higher.

Unfortunately, it turns out that no single sorting algorithm always guarantees to be the best. It really depends on the context, like sorting depth, movement, and other criteria. In most memory-based contexts for simple arrays, quick sort is the best. However, when we have to move a lot of data, sometimes we cannot store the entire thing if you are sorting a database. Therefore, we use a variation of merge sort called external merge sort.

Selecting the best sorting algorithm depends on various factors such as data type, size, and context of usage. Quick sort is efficient for most general sorting scenarios, especially with memory-resident arrays. However, in cases where the dataset is large and cannot fit into memory (like in databases), a modified version of merge sort is used to handle the data efficiently. This highlights that there is no one-size-fits-all algorithm, making the study of different algorithms essential.

Consider cooking for a large event. For a small dinner, a quick preparation method works well (like a quick stir-fry). But if you’re serving hundreds, you need to cook in bulk, which might require slow-cooking methods where ingredients are added in stages. Just as in cooking, different sorting techniques best suit different scenarios.

So, you could even have hybrid algorithms, using divide and conquer where n is large and then when n becomes small you switch over to maybe insertion sort. Many strategies can be adopted to make sorting more efficient, which connects with the earlier discussion about algorithm stability and choice based on context.

Hybrid sorting algorithms utilize the strengths of multiple algorithms based on specific conditions in the data being sorted. For instance, when the dataset is small, insertion sort, which is simple and efficient for small lists, might be used after a quick sort has split the data into manageable parts. Combining strategies can lead to improved performance and efficiency, especially with varying data sizes.

This is akin to a student studying for exams; during regular reviews, they might use quick methods like flashcards but switch to in-depth study sessions for complex subjects when close to the exam. Here, the combination of quick methods and in-depth strategies maximizes understanding.

--