What is stable sorting? Also prove that counting sort is stable.

Stable Sorting

In computer science, a stable sorting algorithm is a sorting algorithm that maintains the relative order of equal elements in the input. This means that if two elements in the input have the same value, their relative order in the output will be the same as their relative order in the input.

Stable sorting algorithms are often used in situations where it is important to maintain the original order of elements, such as when sorting a list of items that have multiple attributes. For example, if you have a list of students with their names and grades, and you want to sort the list by grade, a stable sorting algorithm will ensure that students with the same grade are listed in the same order as they were in the original list.

Counting Sort is Stable

To prove that counting sort is stable, we need to show that if two elements in the input have the same value, their relative order in the output will be the same as their relative order in the input.

Let's consider two elements (x) and (y) in the input list such that (x = y). We know that counting sort works by first creating an array of zeros, called the count array, with a size equal to the maximum value in the input list. Then, for each element in the input list, the count array at the index equal to the value of the element is incremented. After processing all elements in the input list, the count array contains the number of occurrences of each value in the input list.

Next, counting sort uses the count array to determine the final position of each element in the output list. To do this, it starts from the beginning of the input list and iterates through each element. For each element, it adds the count of the element's value in the count array to the current index in the output list. Then, it places the element at the current index in the output list and decrements the count of the element's value in the count array.

Since (x = y), the count of (x) and (y) in the count array will be the same. Therefore, when counting sort places (x) and (y) in the output list, they will be placed at consecutive indices. This means that their relative order in the output list will be the same as their relative order in the input list.

Hence, counting sort is a stable sorting algorithm.