Merge sort uses divide and conquer: it splits the list into two halves, sorts each half recursively, and then merges the sorted halves back together.
It has \(O(n \log n)\) time complexity and uses \(O(n)\) extra space for merging.
Example:
- Input: [8, 3, 5, 4, 7, 6, 1, 2]
- Output: [1, 2, 3, 4, 5, 6, 7, 8]
flowchart TD
A[Start] --> B[Split array in half]
B --> C[Sort left half]
B --> D[Sort right half]
C --> E[Merge sorted halves]
D --> E
E --> F[Sorted array]Python Code:
class Solution:
def mergeSort(self, nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.mergeSort(nums[:mid])
right = self.mergeSort(nums[mid:])
return self.merge(left, right)
def merge(self, left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged