Overview
Merge Sort is a highly efficient, stable, and comparison-based sorting algorithm. It operates by
dividing the unsorted list into smaller sublists until each sublist consists of a single element
(which is trivially sorted). The algorithm then merges these sublists back together in the correct
order to form the sorted list. This divide-and-conquer approach ensures that the list is sorted in a
predictable and efficient manner.
Time Complexity:
Best case: O(n log n) - The time complexity remains O(n log n) in all cases because the list
is always divided in half and merged.
Average case: O(n log n) - The number of comparisons and merging steps remains consistent for
any input order.
Worst case: O(n log n) - The time complexity does not degrade for worst-case scenarios.
Space Complexity: O(n) - It requires additional space to store the sublists, making it
less space-efficient than in-place algorithms.
function mergeSort(list) if length(list) <= 1 return list mid = length(list) div 2 leftHalf = mergeSort(list[0:mid]) rightHalf = mergeSort(list[mid:end]) return merge(leftHalf, rightHalf)function merge(left, right) result = [] while left and right are not empty if left[0] < right[0] append left[0] to result else append right[0] to result end while return result + remaining elements from left + rightSHORT EXPLANATION------------------1. Divide the list into two halves2. Recursively sort both halves3. Merge the two sorted halves4. During merging, compare the first elements of both halves5. Append the smaller element to the result list6. Continue merging until the entire list is sorted