Skip to content

Instantly share code, notes, and snippets.

@jwenjian
Created April 14, 2020 02:23
Show Gist options
  • Save jwenjian/3aa5801940d860b30f464a68bf983897 to your computer and use it in GitHub Desktop.
Save jwenjian/3aa5801940d860b30f464a68bf983897 to your computer and use it in GitHub Desktop.
Merge sort integer array in python
source = [11, 8, 3, 9, 7, 1, 2, 5, 13, 6, 8]
def merge(left, right):
temp = [0] * (len(left) + len(right))
idx_l = 0
idx_r = 0
for i in range(len(temp)):
if idx_l >= len(left):
for k in range(i, i + len(right) - idx_r):
temp[k] = right[idx_r]
idx_r += 1
break
if idx_r >= len(right):
for k in range(i, i + len(left) - idx_l):
temp[k] = left[idx_l]
idx_l += 1
break
if left[idx_l] < right[idx_r]:
temp[i] = left[idx_l]
idx_l += 1
else:
temp[i] = right[idx_r]
idx_r += 1
return temp
def merge_sort(source):
n = len(source)
if n == 1:
return source
if n == 2:
if source[0] > source[1]:
source[0], source[1] = source[1], source[0]
return source
else:
return source
mid = int(n / 2)
return merge(merge_sort(source[:mid]), merge_sort(source[mid:]))
result = merge_sort(source)
print('result = ', result)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment