Skip to content

Instantly share code, notes, and snippets.

@scriptpapi
Last active May 22, 2018 18:39
Show Gist options
  • Save scriptpapi/a977cfe0584bc21ca97224f9a43bf54b to your computer and use it in GitHub Desktop.
Save scriptpapi/a977cfe0584bc21ca97224f9a43bf54b to your computer and use it in GitHub Desktop.
Brute implementation attempt of Merge Sort algorithm from the scratch
# Brute implementation attempt of Merge Sort algorithm from the scratch
from math import ceil
import random
def divide(ListofLists):
newList = list()
for i in range(len(ListofLists)):
if len(ListofLists[i]) > 2:
tmp = ListofLists[i]
divider = int(ceil(len(tmp) / 2))
newList.append(tmp[divider:])
newList.append(tmp[:divider])
else:
newList.append(ListofLists[i])
for i in range(len(newList)):
if len(newList[i]) > 2:
newList = divide(newList)
return newList
def FilterSingles(ListofLists):
singlesList = list()
for i in range(len(ListofLists)):
if len(ListofLists[i]) == 1:
if len(singlesList) == 0:
singlesList.append(ListofLists[i][0])
else:
#If it's not empty
for j in range(len(singlesList)):
print("Iteration number:", j)
try:
if ListofLists[i][0] < singlesList[j]:
print("ListofLists[i][0]> ", ListofLists[i][0], "singlesList[j]> ", singlesList[j])
singlesList = singlesList[:j] + ListofLists[i] + singlesList[j:]
else:
print("cont called: ")
continue
except IndexError:
print("except called: ", ListofLists[i][0])
singlesList.append(ListofLists[i][0])
print(singlesList)
def mergeSort(in_list):
mergeList = list()
divider = int(ceil(len(in_list)/2))
mergeList.append(in_list[:divider])
mergeList.append(in_list[divider:])
mergeList = divide(mergeList)
print(mergeList)
FilterSingles(mergeList)
testList = random.sample(range(1, 100), 20)
mergeSort(testList)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment