Merge Sort
ARRAY
SORTING

Problem

Implement the merge sort algorithm to sort an array of integers in ascending order. The function mergeSort should take an array of integers as input and return a new array containing the sorted integers.

Algorithm

  1. Divide the unsorted array into two approximately equal parts.
  2. Recursively sort each sub-array.
  3. Merge the two sorted sub-arrays into a single sorted array.

Examples:

mergeSort([9,4,7,3,5,8,1,6,2]) // returns [1,2,3,4,5,6,7,8,9]

Complexity

  • Time Complexity: O(n log n) for all cases (best, average, and worst).
  • Space Complexity: O(n), due to the additional space needed for merging.
Loading...