1
\$\begingroup\$

I'm starting to study sorting algorithms in Python. Merge Sort has a complexity at best and worst cases \$\mathcal{O}(n\log{}n)\$, I want generation a list where Merge Sort is slow but I would some complication. Could you help me with this problem?

This is the code:

def mergeSort(l):

    #print("Splitting ",l)
    if len(l)>1:
        mid = len(l)//2
        lefthalf = l[:mid]
        righthalf = l[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)


        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                l[k]=lefthalf[i]
                i=i+1
            else:
                l[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            l[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            l[k]=righthalf[j]
            j=j+1
            k=k+1
    #print("Merging ",l)
    return
\$\endgroup\$
  • \$\begingroup\$ That's not really the purpose of this site. Take a look at this question for how to create a worst case input for merge sort. \$\endgroup\$ – ferada Aug 21 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.