0%

LEETCODE MergeSort, QuickSort

Mergesort leetcode 912

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import math
class Solution:

def sortArray(self, nums: List[int]) -> List[int]:
# merge sort, divide and conquer
if len(nums) <= 1:
return nums

# let length of left < length of right
median = math.floor(len(nums)/2)
left = self.sortArray(nums[:median])
right = self.sortArray(nums[median:])

# store sorted array
temp = []
i, j = 0,0
while (i <len(left)) and (j <len(right)):
if left[i] > right[j]:
temp.append(right[j])
j+=1
else:
temp.append(left[i])
i+=1

if left or right:
temp = temp+left[i:]+right[j:]
return temp