Merge Sort
Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts each half, and then merges the sorted halves to produce the final sorted array. It has an average-case and worst-case time complexity of O(n log n).