17.1.7. Naive vs. Complex Sorting Algorithms

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. So, in other words we do not want to disturb the sorting of alphabetical orders.

Stable sorting is a method where the order of similar items, which were sorted previously by another criterion, remains unchanged. In this case, when sorting names by marks, we want people who got the same score (like Ashwin and Chander) to retain their original alphabetical order. For instance, if Ashwin comes before Chander in alphabetical order, then after sorting by marks (when both received 60 marks), Ashwin should still come before Chander.

Imagine you are organizing a book shelf. You initially sorted books by title, but then someone gives you a list to further sort them by author. If two books have the same author, you want their original order by title to remain intact. If this function fails, it would be like mixing up books on the shelf where you cannot find them easily.

So, quick sort as shown is not a stable operation... So, any kind of long distance swapping is very dangerous for stability.

Quick sort is an example of a sorting algorithm that is not stable. This means that during its operation of rearranging numbers, it may swap elements in a way that disrupts their original order if they are considered equal. For example, if Ashwin and Chander have the same marks, quick sort might put Chander before Ashwin after sorting, losing the alphabetical order.

Think of organizing a group of friends for a game. If you swap two friends who have similar skills but originally stood in a specific order based on another criterion (like how long they've known each other), the new arrangement might not respect the original grouping, leading to confusion. This analogously describes how stability in sorting is lost.

What about merge sort? Well, merge sort would normally be stable provided... that is why we said that in the case, A i is less than or equal to B j, we pick from A and only…

Merge sort is a stable sorting algorithm because it preserves the order of equal elements. When merging two sorted lists, if two elements are the same, merge sort will always take the element from the first list (let's call it A) before touching the second list (let’s call it B). This ensures that if two items in the list are equal, their original ordering is maintained.

Imagine two people in a race having equally fast times. If we were to record their positions based on their race times, we would want to retain their original lane positions (the first lane before the second) whenever possible. In merge sort, this is guaranteed by always picking the 'first' from A before picking from B, hence maintaining their initial placement.

So, very often a question is asked which sort is best... In most memory-based context for simple arrays, quick sort is the best.

There isn’t one sorting algorithm that is the best in all scenarios; it greatly depends on the context such as the size of the data, the environment (e.g., memory constraints), and other specific criteria. Quick sort is favored for smaller arrays and simple data situations, while variations like external merge sort are necessary when data sets exceed memory capacity.

Imagine you need to choose a vehicle for different tasks. A small car might be great for driving in the city (quick sort), but a large truck is better for moving goods long distances (external merge sort). Different circumstances demand different tools, much like sorting algorithms.

the simplicity of a naive algorithm beats the complexity of a complicated value. So, you could even have hybrid algorithms...

Sometimes, a straightforward or 'naive' sorting algorithm can work better for small datasets than more complex ones. In scenarios where data size changes, some sorting implementations use a combination of algorithms, like quick sort for larger datasets and switching to insertion sort when the size is smaller, optimizing the process.

Think about cooking. If you're making a small meal (small dataset), a simple recipe is efficient and quick. However, for a large feast, you might use more complex methods or even combine recipes to manage better. Similarly, combining sorting algorithms can lead to effective solutions depending on the size and requirement.

--