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, "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.