17.1.5. Cost of Movements in Sorting

So, one of the important criteria that we should not forget is that, sorting often happens in phases... So, this is called stable sorting that is there was, so very often when you are sorting a sorting on one attribute, but there may be other attributes.

Stable sorting is a characteristic of certain sorting algorithms where equal elements maintain their relative positions after sorting. For example, when sorting by marks and names at the same time, if two students have the same marks, their order by names should not be disturbed. This is crucial when data has multiple attributes.

Imagine organizing a group of people by height, but you want to keep them in alphabetical order by their names if their heights are the same. Stable sorting ensures this order is preserved.

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

Some sorting algorithms, like quicksort, are not stable. This means that when elements are swapped during the sorting process, the original order of items with equal key values could be disrupted. This is particularly true for operations that involve moving items over long distances in the list, which can lead to instability.

Think of a game where players are sorted by their scores, and if a player is moved far away each time a score change happens, they may end up standing in a different order with respect to their friends, which can feel unfair.

What about merge sort? Well, merge sort would normally be stable provided… If you have made the mistake of writing less than and then we use greater than equal to, select from B, then when they are equal, we first pick from B and not from A and that would create instability.

Merge sort is usually a stable sorting algorithm because during the merging process, if two elements are equal, the one that came first in the original array is chosen first to maintain stability. If not done correctly, this order could be disrupted, leading to instability in sorting.

Picture a library where books are sorted by both title and author. If two books have the same title but different authors, merge sort ensures that their original order on the shelves is preserved even after sorting.

So, another criteria, which is related to what we just saw is that we have only concentrated on the number of steps... So, imagine when you sorting something by hand, supposing you are sorting a bunch of heavy cartons...

When considering sorting algorithms, it’s important to think about the cost of moving elements. For instance, moving elements that are far apart might have a higher cost than moving adjacent elements. This aspect is crucial in scenarios where data resides across different locations, such as multiple server systems.

If you're lifting heavy boxes in a warehouse, moving one box from one aisle to another far away is much harder than simply shifting a box next to it. Thus, efficient sorting in terms of movement cost can save energy and time.

So, very often a question is asked which sort is best... So, the very fact that many of these algorithms where studied, shows that in different context you might need to use one or the other idea in order to make things work better.

There is no one-size-fits-all sorting algorithm that is the best in every scenario. The effectiveness of sorting algorithms like quicksort or merge sort can depend on the specifics of the data and the context in which they are used. Factors such as data size, memory availability, and movement costs play a role in determining which algorithm should be chosen.

Similar to how you might choose different tools for different jobs, like using a hammer for nails and a wrench for bolts, the choice of sorting algorithm depends on the specific requirements of the sorting task at hand.

--