Skip to content

Instantly share code, notes, and snippets.

@scriptpapi
Created May 22, 2018 22:26
Show Gist options
  • Select an option

  • Save scriptpapi/610cfe804a2d5f0e97761183a9712a52 to your computer and use it in GitHub Desktop.

Select an option

Save scriptpapi/610cfe804a2d5f0e97761183a9712a52 to your computer and use it in GitHub Desktop.
Simple merge sort implementation
# Simple merge sort implementation
# reference: http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html
import random
def mergeSort(iList):
if len(iList) > 1:
mid = len(iList) // 2
lList = iList[:mid]
rList = iList[mid:]
mergeSort(lList)
mergeSort(rList)
l = 0
r = 0
i = 0
while l < len(lList) and r < len(rList):
if lList[l] < rList[r]:
iList[i] = lList[l]
l += 1
else:
iList[i] = rList[r]
r += 1
i += 1
while l < len(lList):
iList[i] = lList[l]
l += 1
i += 1
while r < len(rList):
iList[i] = rList[r]
r += 1
i += 1
return iList
# Testing
testList = random.sample(range(1, 100), 5)
print(testList)
print(mergeSort(testList))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment