Backend Engineer
Senior
programming
Implement a function to sort an array using the Merge Sort algorithm. The function should return the sorted array.
Example 1:
Input: arr = [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]
Example 2:
Input: arr = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Constraints:
- 1 <= arr.length <= 10^6
- -10^6 <= arr[i] <= 10^6.
```
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
```
Trusted by 100+ professionals preparing for interviews
Trusted by 100+ professionals
50+ Company Question Banks
5+ Supported Languages
Practice More Questions Like This
Generate unlimited interview questions with structured answers, code runner, and AI-powered walkthroughs.
Get Started Free