Stable and unstable sorting algorithms

Sorting is a fundamental operation in computer science that involves arranging items or data elements in a specific order. Efficient sorting algorithms are essential for optimizing various computational tasks, such as searching, data analysis, and information retrieval.

Among these algorithms, a key distinction exists between stable and unstable sorting methods. This answer explores the fundamental differences between these two categories and examines their strengths and use cases.

Stable sorting

In a stable sorting algorithm, data is sorted in a way that preserves the original order of elements having equal keys. This means that if two elements have the same key, the one that appeared earlier in the input will also appear earlier in the sorted output. For instance, if element A[i] and element A[j] have the same key and i < j, then in sorted order, A[i] should come before A[j].

Stable sorting algorithms

There are numerous examples, but the most common ones include:

• Merge sort: It divides the dataset into smaller subarrays, sorts them individually, and then merges them to obtain the final sorted result. Its time complexity is O(n log n).

• Insertion sort: It divides the array into sorted and unsorted portions. It compares the unsorted elements with the sorted elements and places them in their correct positions. Its time complexity is O(n ²).

• Bubble sort: It iterates the array repeatedly until completely sorted, compares the adjacent elements in each iteration, and swaps them if they are not in the correct order. Its time complexity is O(n ²).

• Counting sort: It counts the occurrences of the elements in the dataset and uses this information to sort them in increasing order. Its time complexity is O(n+b).

• Radix sort: It sorts the numbers by sorting each digit from left to right, resulting in the sorted data. Its time complexity is O(d*(n+b)).

Unstable sorting

In an unstable sorting algorithm, data is sorted so that the order of elements with equal keys is not preserved after sorting. For instance, if element A[i] and element A[j] have the same key and i < j, then in sorted order, there is a possibility that A[j] can come before A[i].

Unstable sorting algorithms

There are numerous examples, but the most common ones include:

• Quick sort: It uses a recursive approach to divide an array into subarrays. In every recursive call, it chooses a pivot element, places it in its correct sorted position, and arranges the elements so that those smaller than the pivot are placed before it. In contrast, larger ones are placed after it. Its time complexity is O(n log n).

• Heap sort: It uses the max heap data structure, extracts the maximum element repeatedly, and places it at the end of the list, resulting in the sorted data. Its time complexity is O(n log n).

• Shell sort: It divides the list into sublists, uses an insertion sort algorithm to sort each sublist, and gradually reduces the gap between elements to sort the entire list efficiently. Its time complexity is O(n log n).

Now that we understand stable and unstable algorithms, let's review a real-world example to enhance our knowledge.

Example

Our data consists of students' name and their exam scores. We have to sort based on the scores of the students in ascending order. Here, the score is the key and the student's name is the value.

Charlie and John have the same score, so when sorted, Charlie's data should be above John's to maintain stability.

In unstable sorting, the order of data after sorting is not preserved, but the sorted output is still correct.

Conclusion

It depends on the user's preference and the nature of the data, whether to choose a stable or an unstable sorting algorithm. If the order of sorted output and data consistency is important, the user should opt for a stable algorithm. When the order of sorted output is irrelevant, the user can use unstable sorting algorithms.