# Does my Algorithm Qualify as MergeSort?

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "version" of the algorithm from there.

I did this with MergeSort recently, and I got an algorithm that for what I can tell works but I'm not sure it runs in O(nlogn) time like MergeSort does. Here's my code, it's in Python:

def mergeSortAlgorithm(x):

listOfLists = []

for i in range(len(x)):
temp = [x[i]]
listOfLists.append(temp)                          #I first put every item in the array into
#its own list, within a larger list -> divide step

#so long as there is more than one sorted list, then we need to keep merging
while(len(listOfLists) != 1):
j = 0

#for every pair of lists in the list of lists, we need to merge them
while(j < len(listOfLists)-1):
tempList = merge(listOfLists[j], listOfLists[j+1])
listOfLists[j] = tempList
del listOfLists[j+1]                          #I shift the new list to index j, and delete the second list from the now-merged pair at index j+1
j = j+1                                       #increment the value of j, basically a counter
print(listOfLists)

print(listOfLists[0], "is sorted!")

def merge(a, b):                                          #function to merge two lists in order
newList = []
count1, count2 = 0, 0

#basically, walk through each list, adding whichever element is smallest
while((count1 < len(a)) and (count2 < len(b))):

if(a[count1] > b[count2]):
newList.append(b[count2])
count2 = count2 + 1                           #update the counter along b

elif(a[count1] < b[count2]):
newList.append(a[count1])
count1 = count1 + 1                           #update the counter along a

elif(a[count1] == b[count2]):                     #if they're equal, add the value from a first
newList.append(a[count1])
newList.append(b[count2])
count1, count2 = count1 + 1, count2 + 1       #update the counter on each

if(count1 < len(a)):                                  #if the while loop exited with left-over values in a, add them
for f in range(count1, len(a)):
newList.append(a[f])
elif(count2 < len(b)):                                #do the same for b - the values are already in order so you're good
for k in range(count2, len(b)):
newList.append(b[k])

return newList


The algorithm correctly sorts what I give it, but I'm thinking that the runtime is more like $O(\log n\cdot \log n\cdot n)$ because the outer while loop in mergeSortAlgorithm() will do $\log n$ passes, as will the inner while loop, and the merge() algorithm will take in total $n$ operations.

Is that right? If so, in what respect does my algorithm differentiate from MergeSort? (i.e. where am I going wrong?)

Thanks so much for your help, please let me know if you have further questions I can help explain.

• Is there a reason you didn't implement this recursively? That is how mergesort is traditionally done and it would likely make your algorithm and its complexity easier to understand. – jmite Jun 21 '17 at 17:03
• Not for any specific reason, no, and actually I thought the runtime might be easier to analyze iteratively but then again I could be wrong :/ – dgamz Jun 21 '17 at 17:09
• @dgamz Sidenote: There are a lot of issues with your code (not logic) as well. You should get a code review – Peeyush Kushwaha Jun 21 '17 at 17:38
• Please replace your code with pseudocode, aiming to make it shorter. As for whether this "counts" as mergesort, there is no legal definition of mergesort. Mergesort is a vague concept whose exact definition is up to debate. – Yuval Filmus Jun 21 '17 at 18:44
• @YuvalFilmus I was referring more to whether it matches the runtime of MergeSort, but your critique is noted – dgamz Jun 21 '17 at 20:44