Merge Sort

Explanation

- **Merge Sort** is a divide-and-conquer sorting algorithm. It divides the list into smaller sublists, sorts each sublist recursively, and then merges the sorted sublists to produce the final sorted list.

-

• Steps:

  • If the list has more than one element, split it into two halves.
  • Recursively apply the same operation on both halves.
  • Merge the two sorted halves into a single sorted list.
  • Repeat the process until the list is sorted.

• Time Complexity:

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