Merge Sort

Stable Sorting Algorithms Stable sorting algorithms are algorithms that maintain the relative order of equally valued elements in its sorted output. This means that if two elements are equal in value, the element that appears first in the original list will appear first in the sorted list. Use Case One use case when sorting a list of objects by multiple keys. If the list is sorted by one key and then sorted by another key, the relative order of the first key will be maintained in the second sort....

Merge Sort Merge Sort is a divide-and-conquer algorithm that divides the input list into two halves, recursively sorts the halves, and then merges the sorted halves. This algorithm is efficient for larger lists and is a stable sorting algorithm that guarantees $O(n \log n)$ time complexity. Key Points Time Complexity: $O(n \log n)$ Space Complexity: $O(n)$ Process: Divide: The input list is divided into two halves Conquer: The two halves are recursively sorted Merge: The sorted halves are merged back together in sorted order Features:...