Merge Sort not working with an array bigger than 10^7 elements

user_9530583 0
Viewed 125

My algorithm works perfectly for an array of up to 10^6 elements, even though it is not that efficient it does it's job. The array which I want it to be sorted is randomly generated. I read from a file the number of elements the array will have and the maximum value and then create the list.

def mergeSort(listaNumere):
    n = len(listaNumere)
    if n == 1:
        return listaNumere
    mij = n//2
    stanga = []
    for i in range (0, mij):
        stanga.append(listaNumere[i])
    dreapta = []
    for i in range(mij, n):
        dreapta.append(listaNumere[i])

    #stanga = listaNumere[:mij]
    #dreapta = listaNumere[mij:]

    stanga = mergeSort(stanga)
    dreapta = mergeSort(dreapta)

    return merge(stanga, dreapta)

def merge(stanga, dreapta):
    aux = []
    while len(stanga) != 0 and len(dreapta) != 0:
        if stanga[0] < dreapta[0]:
            aux.append(stanga[0])
            del stanga[0]
        else:
            aux.append(dreapta[0])
            del dreapta[0]

    while len(stanga) != 0:
        aux.append(stanga[0])
        del stanga[0]

    while len(dreapta) != 0:
        aux.append(dreapta[0])
        del dreapta[0]

    return aux

The program has been running in the background for the past 30 minutes and has not finished sorting the array.

How can i make the program more efficient so that it does not take that much time to run?

Tried this:

def merge(stanga, dreapta):
    aux = []
    i,j = 0,0
    while i < len(stanga) and j < len(dreapta):
        if stanga[i] < dreapta[j]:
            aux.append(stanga[i])
            i += 1
        else:
            aux.append(dreapta[j])
            j += 1

    while i < len(stanga):
        aux.append(stanga[i])
        i += 1

    while j < len(dreapta):
        aux.append(dreapta[i])
        i += 1

    return aux
mergesort arrays python
3 Answers

Delete operation has O(N) complexity, which will inevitably make program execution very slow.
Get rid of all del dreapta[0] and del stanga[0] statements and refactor your merge logic using two pointers.

def merge(stanga, dreapta):
    aux = []
    i,j = 0,0
    while i < len(stanga) and j < len(dreapta):
        if stanga[i] < dreapta[j]:
...
user_93507200

Make a one time copy of the array. Alternate direction of merge with level of recursion to avoid excess copying of data. This example code takes a bit over 1 minute to sort 10^7 integers. This is a case where Python is slow. The same code in C | C++ is over 50 times faster.

def sort(a):
    if(len(a) < 2):                     # if nothing to do, return
        return
    b = a[:]                            # b = copy of a
    sortr(b, a, 0, len(a))              # merge sort

def sortr(b, a, beg, end):              # merge sort
    if((end - beg) < 2):                # if < 2 elements
        return                          #   return
    mid = (beg+end)//2                  # set mid point
    sortr(a, b, beg, mid)               # merge sort left  half to b
    sortr(a, b, mid, end)               # merge sort right half to b
    mrg(b, a, beg, mid, end)            # merge halves   from b to a

def mrg(a, b, ll, rr, ee):              # merge a pair of runs from a to b
    o = ll                              # o = b[]        index
    l = ll                              # l = a[] left   index
    r = rr                              # r = a[] right  index
    while True:
        if(a[l] <= a[r]):               # if a[l] <= a[r]
            b[o] = a[l]                 #   copy a[l]
            o += 1
            l += 1
            if(l < rr):                 #   if not end of left run
                continue                #     continue (back to while)
            b[o:ee] = a[r:ee]           #   else copy rest of right run
            return                      #     and return
        else:                           # else a[l] > a[r]
            b[o] = a[r]                 #   copy a[r]
            o += 1
            r += 1
            if(r < ee):                 #   if not end of right run
                continue                #     continue (back to while)
            b[o:ee] = a[l:rr]           #   else copy rest of left run
            return                      #     and return
user_32820560

Using append and del is inefficient as the intermediary arrays need to be reallocated and/or shifted. You should instead allocate the intermediary arrays to the right size and store the elements at the proper indexes:

def mergeSort(listaNumere):
    n = len(listaNumere)
    if n < 2:
        return listaNumere
    mij = n // 2
    stanga = listaNumere[:mij]
    dreapta = listaNumere[mij:]

    stanga = mergeSort(stanga)
    dreapta = mergeSort(dreapta)

    return merge(stanga, dreapta)

def merge(stanga, dreapta):
    slen = len(stanga)
    dlen = len(dreapta)
    aux = [0] * (slen * dlen)
    i = 0
    j = 0
    k = 0
    while i < slen and j < dlen:
        if stanga[i] <= dreapta[j]:
            aux[k] = stanga[i]
            i += 1
            k += 1
        else:
            aux[k] = dreapta[j]
            j += 1
            k += 1

    if i < slen:
        aux[k:] = stanga[i:]
    else
        aux[k:] = dreapta[j:]
    return aux
user_45932670
Related