Which of the following algorithms is considered stable?

Merge Sort is considered a stable sorting algorithm because it maintains the relative order of records with equal keys. In a stable sort, if two elements are equal, their order in the sorted output remains the same as in the input. This property is particularly important when sorting data structures where the original order carries significance, such as sorting entries in a database.

The stability of Merge Sort arises from its divide-and-conquer approach. When merging two sorted halves, it compares the elements and places them in the output array in such a way that if two elements are equal, the one from the left half (which was encountered first) is placed before the one from the right half. Thus, equal elements retain their original order.

Other sorting algorithms can have different characteristics:

• QuickSort, while efficient, does not guarantee stability since the partitioning process can rearrange equal elements randomly.

• Heap Sort is also unstable; it can change the relative order of equal elements due to the way elements are arranged in the heap structure.

• Selection Sort is not stable either, as it can swap elements that are equal, resulting in a potential change of their relative positions.

This makes Merge Sort a favorable choice when stability is a necessity in sorting operations.