Merge Sort Algorithm

Merge Sort is a divide-and-conquer sorting algorithm that divides the unsorted list into n sublists, each containing one element, and then merges the sublists to produce a sorted list. It follows a recursive approach where the list is repeatedly split until it consists of single elements, and then merged back together in a sorted manner.

Algorithm

1. Divide the unsorted list into n sublists, each containing one element.
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.
3. Each merge operation involves comparing the elements of the sublists and combining them in sorted order.
4. Continue merging until the entire list is sorted.

Time Complexity

Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)