Merge Sort A bottom-up divide-and-conquer sorting algorithm O(n log n)average-(and worst-)case performance O(n)additional space requirement Merging two arrays is the core computation 6 -18-2 -4 3 6 -7-2-18Merge Sort • A bottom-up divide-and-conquer sorting algorithm • O(n log n) average - (and worst - ) case performance • O(n) additional space requirement • Merging two arrays is the core computation