Does my Algorithm Qualify as MergeSort?

Question

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.

Answer 1

I agree in principle with the comment suggesting that a recursive implementation would be simpler to analyze, and the other comment mentioning that there is no "legal" definition of such an algorithm like merge sort.

However, I think you've done yourself a favor (in terms of your learning objectives) by attempting to implement this bottom-up (rather than top-down), iterative (rather than recursive) merge sort, which is essentially what you have above. I think this shows good understanding on your side. Perhaps you can attempt to implement an in-place version, rather than creating a newList (etc.).

Typically, you would divide the input into two equal parts, sort each, and then merge. Instead, you start "at the leaves" and progress up the chain -- merging singletons, then merging pairs, then merging pairs of four items, etc. Each iteration of your loop "looks like" a particular depth-level in the recursive tree of typical merge sort.

That said, your delete-based approach isn't the most suited for arrays (which, it seems, CPythons lists are under the hood -- a Google search found this) at all in terms of cost. You should be able to fix this, but when doing so, be careful to handle non-power-of-two input sizes.