Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.
Examples:
{1} is sorted to {1}
{1, 2, 3} is sorted to {1, 2, 3}
{3, 2, 1} is sorted to {1, 2, 3}
{4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}
class Solution(object):
def mergeSort(self, array):
if len(array) <= 1:
return array
mid = len(array)/2
left = self.mergeSort(array[:mid])
right = self.mergeSort(array[mid:])
return self.merge(left,right)
def merge(self,left,right):
l,r = 0,0
res = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
res += left[l:]
res += right[r:]
return res
