Skip to content

Instantly share code, notes, and snippets.

@liyunrui

liyunrui/mergeSort.py

Last active Mar 14, 2021
Embed
What would you like to do?
leetcode-sorting
def merge_sort(arr):
"""
Thought Process:
1.Divide the array into two halves
2.recursively call merge sort for left half and call merge sort for right half.
What this return is sorted array already.
3.stop merge process until size of array becomes 1
Time Complexity Analysis:
1. Totall running time would be O(n*logn). And, log n comes from maximum height of recursion tree we created. and n comes
from merge process that we need to visit n elements.
2. The recursion tree consists of O(n*logn) levels, and processing each level take O(n).
Test Case:
Given array = [1,3,2]
[1,3,2]
/ \
[1] [3,2]
/\
[3] [2]
Given array = [4,3,2,1]
[4,3,2,1]
/ \
[4,3] [2,1]
/\ /\
[4] [3] [2] [1]
\/ \/
[3,4] [1,2]
\ /
[1,2,3,4]
S:S(log n). In worse case, O(n). So, it's not in-place sort.
Ref:
https://www.geeksforgeeks.org/merge-sort/?ref=lbp
"""
if len(arr) > 1:
mid = len(arr) // 2
l = arr[:mid]
r = arr[mid:]
l = merge_sort(l)
r = merge_sort(r)
# merge
value = []
# i is pointer of left half and r is right pointer of right half.
i=j=0
while i < len(l) and j < len(r):
if l[i] < r[j]:
value.append(l[i])
i+=1
else:
value.append(r[j])
j+=1
while i < len(l):
value.append(l[i])
i+=1
while j < len(r):
value.append(r[j])
j+=1
return value
return arr
def mergesort(self, nums):
n = len(nums)
if n > 1:
mid = n // 2
left = self.mergesort(nums[:mid])
right = self.mergesort(nums[mid:])
return self.merge(left, right)
return nums
def merge(self, left, right):
values = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] > right[j]:
values.append(right[j])
j+=1
else:
values.append(left[i])
i+=1
while i < len(left):
values.append(left[i])
i += 1
while j < len(right):
values.append(right[j])
j += 1
return values
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment