Merge sort is a divide-and-conquer sorting algorithm that works by dividing the unsorted list into n sublists, then repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining.
The time complexity of merge sort is O(n log n), where n is the number of elements in the array or list being sorted. This is because the algorithm divides the input into halves in each recursive step, and each
step takes O(n) time to merge the two sorted sub-arrays back into a single sorted array.