mergeSort

Hard · Recursion · 1 test cases

Implement the merge sort algorithm to sort an array of numbers in ascending order.

Examples

mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]) → [1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]

Starter code

function mergeSort(arr) {

}

Complexity of the optimal solution

Time O(n log n), space O(n). Merge sort is a divide-and-conquer algorithm. It recursively divides the array in half (log n levels of recursion). At each level, it merges the subarrays, which takes O(n) time. This results in a time complexity of O(n log n). It requires extra arrays for merging, leading to O(n) space complexity.

Solve mergeSort in the browser