Merge Sort in place for python (Cant find what is wrong)

Question

I was reading about merge sort(In place) in my algorithm book (Intro to algorithms 3rd edition Cormen), and I decided to implement it in Python. The problem is that I can't find what I am doing wrong... I saw some code in C++, but even with that I can't fix it.

Here is my code:

def MERGE(A,start,mid,end):
    L=[0]*(mid - start + 1)
    for i in range(len(L) - 1):
        L[i] = A[start+i]
    L[len(L) - 1] = 100000 # centinel, (fix)
    R=[0]*(end - mid + 2)
    for j in range(len(R) - 1):
        R[j] = A[mid+j]

    R[len(R) - 1] = 100000
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if(L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1   

def mergeSort(A,p,r):
    if p < r:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)
        MERGE(A,p,mid,r) 

A  = [20, 30, 15, 21, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)]

When I run the code I have some index problems:

File "myrealmerge.py", line 9, in MERGE
R[j] = A[mid+j]
IndexError: list index out of range

I know that this my be a "dumb question" and that there is some related post, but I tried the suggestions in there and It does not work for me...

Can anyone help me? T Thanks!

How is this in place? You're using additional storage for `L` and `R`. — agf, Sep 30 '13 at 02:13
Upon further inspection, I actually think your problem is in the usage of your `range` function just above the line where you get an `IndexError`. You are aware that `range(len(A))` where A is a list, actually returns a list of *all* valid indices of A? You don't need to do `range(len(R) - 1)`. And as agf noted, this is not in-place. — Shashank, Sep 30 '13 at 02:20
Ok, what I mean by "in place" is that i dont want to use a another Array Result to have the information. (Not another copy of A in Other array but with the sorted elements). @ShashankGupta What you mean by that I dont need to do range(len(R) - 1)?? What I can do? — Edwardo, Sep 30 '13 at 02:30

lancif · Accepted Answer · 2013-10-03T23:48:29.193

7

This code works fine:

def MERGE(A,start,mid,end):
    L = A[start:mid]
    R = A[mid:end]
    i = 0
    j = 0
    k = start
    for l in range(k,end):
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
print A

I tried to minimize the change from your code.

Good luck!

(Added)

You can check the dividing process by using this code.

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid:r]
        mergeSort(A,p,mid)
        mergeSort(A,mid,r)
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

The result is as follows:

[20, 30, 21, 15] [42, 45, 31, 0, 9]
[20, 30] [21, 15]
[20] [30]
[21] [15]
[42, 45] [31, 0, 9]
[42] [45]
[31] [0, 9]
[0] [9]

This is what we want. However, 'mid+1' makes invalid result. Here is the test code:

def MERGE(A,start,mid,end):
    # Do nothing
    pass

def mergeSort(A,p,r):
    if r - p > 1:
        mid = int((p+r)/2)
        print A[p:mid],A[mid+1:r]    # Changed
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)         # Changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))

result:

[20, 30, 21, 15] [45, 31, 0, 9]
[20, 30] [15]
[20] []
[45, 31] [9]
[45] []

(Added)

Here is a code using 'mid+1':

# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
    return origin_list[left_index:right_index+1]


def MERGE(A,start,mid,end):
    L = get_partial_list(A,start,mid)
    R = get_partial_list(A,mid+1,end)
    i = 0
    j = 0
    k = start
    for l in range(k,end+1):            # changed
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  

def mergeSort(A,p,r):
    if r - p > 0:                          # changed
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)             # changed
        MERGE(A,p,mid,r)

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1)                 # changed
print A

I've added new indexing function. Is this the code you expected?

edited Oct 03 '13 at 23:48

answered Sep 30 '13 at 03:33

lancif

737
1
8
17

Thanks!! I have a doubt with the indices: why in mergeSort you dont pass mid+1 in the second recursive call (it does not work if I pass the + 1)?? Also, did you know ehre I can find some article explaining iterative merge sort?? I have never seen that! (if the code is in python, better for me) – Edwardo Sep 30 '13 at 14:54
@Edwardo: I added explanation about 'mid+1'. – lancif Sep 30 '13 at 23:44
@Edwardo: I'm sorry but I don't know where the code is. However, I think you can implement the iterative version from the recursive version. (reference: http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) – lancif Sep 30 '13 at 23:51
Many Many thnaks, the problem is that I (because of my algorithm book) uses mid+1 and len(A) (it begins in zero).But as a C++ programmer, adn the implementation I have seen, they use mid+1 and len(A)-1. I am triyng to change the code in that way, but I dont know how to do it exactly... I understand that the slice copy ( [:] ) is inclusive (left index) and exclusive (right index). But even that (and using your debug method) cant achieve it... Can you help me? (I am a bit ashamed right now :/ ) – Edwardo Oct 03 '13 at 03:18
@Edwardo: I think that the indexing('mid', 'mid+1') is not important. The important thing is concept of the algorithm. Because of the python's indexing policy(exclude right index), I used 'mid'. You can make a python code that using 'mid+1', but you should make your own indexing function(to include the right index). Do not get stuck with the pseudo code. Follow the concept! – lancif Oct 03 '13 at 23:18
@Edwardo: I've added a code that using 'mid+1'. Do I understand your intention correctly? – lancif Oct 03 '13 at 23:50
Yes! thank you! but, Although this looks great, the first one (without mid+1) looks more natural for a python programmer right? I mean which one you prefer? – Edwardo Oct 04 '13 at 15:32
@Edwardo: Yes, the first one is more natural for python programmers. I also prefer the first one. Good luck! – lancif Oct 04 '13 at 23:41
1

A[start:mid] is a copy, so this is unfortunately not in place. – B. M. Oct 30 '15 at 17:37
Space complexity change for Merge sort and In-place Merge sort. the above is not in place merge sort. [sample](https://www.geeksforgeeks.org/in-place-merge-sort/). – Kiran Kumar Kotari Apr 17 '19 at 12:19
What does "p" mean in `mergesort(A, p, r)` – AbstProcDo May 26 '19 at 00:41

OrangeFish · Answer 2 · 2019-06-16T15:28:02.127

The solutions provided by lancif and krishna Prasad dont not have space complexity O(1).

Here is algorithm in place merge sorting for Py3 with space complexity O(1). The main function sort_imerge uses 2 auxiliary functions wmerge and wsort.

This solution based on C code that discussed on: other SO topic and on good C implementation Also you can find full Python code with doctests here

def sort_imerge(Seq, l=0, u=None):
    """ Merge sorting, mutable input. 
    Input sequence changed in place. 

    Time: O(n * log n)
        log n -- levels
        n -- elements on each level must be merged

    Space (additional): O(1) 
        input changed in place

    Returns None

    """
    u = len(Seq) if u is None else u
    if  u - l > 1:
        m = l + (u - l) // 2
        w = l + u - m  
        wsort(Seq, l, m, w)
        while w - l > 2:
            n = w
            w = l + (n - l + 1) // 2
            wsort(Seq, w, n, l)
            wmerge(Seq, l, l + n - w, n, u, w)
        n = w
        while n > l: # fallback to insert sort
            for m in range(n, u):
                if Seq[m-1] > Seq[m]:
                    Seq[m-1], Seq[m] = Seq[m], Seq[m-1]
            n -= 1

def wmerge(Seq, i, m, j, n, w):
    """Merge subarrays [i, m) and [j, n) into work area w.
    All indexes point into Seq.
    The space after w must be enough to fit both subarrays.
    """
    while i < m and j < n:
        if Seq[i] < Seq[j]:
            Seq[i], Seq[w] = Seq[w], Seq[i]
            i += 1
        else:
            Seq[j], Seq[w] = Seq[w], Seq[j]
            j += 1
        w += 1
    while i < m:
        Seq[i], Seq[w] = Seq[w], Seq[i]
        i += 1
        w += 1
    while j < n:
        Seq[j], Seq[w] = Seq[w], Seq[j]
        j += 1
        w += 1

def wsort(Seq, l, u, w):
    """Sort subarray [l, u) and put reuslt into work area w.
    All indexes point into Seq.
    """
    if  u - l > 1:
        m = l + (u - l) // 2
        sort_imerge(Seq, l, m)
        sort_imerge(Seq, m, u)
        wmerge(Seq, l, m, m, u, w)
    else:
        while l < u:
            Seq[l], Seq[w] = Seq[w], Seq[l]
            l +=1
            w +=1

score 0 · Answer 3 · answered Jul 19 '16 at 03:09

Recursively split the array into left and right part and then merge it as per your requirements i.e ASC or DESC, Check the below code:

def merge_sort(a):
    if len(a) <= 1:
        return a

    left = [];
    right = [];

    mid = len(a)/2

    left = a[0:mid]
    right = a[mid:(len(a))]

    print left
    print right
    #exit()

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        lv = left[0]
        rv = right[0]
        if lv <= rv:
            result.append(lv)
            left.pop(0)
        else:
            result.append(rv)
            right.pop(0)
    while len(left) > 0:
        result.append(left.pop(0))

    while len(right) > 0:
        result.append(right.pop(0))

    return result

A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]

print A
print merge_sort(A)

For understanding I have printed the intermediate partitioned array have a look into the output:

[20, 30, 21, 15, 42, 45, 31, 0, 9]
[20, 30, 21, 15]
[42, 45, 31, 0, 9]
[20, 30]
[21, 15]
[20]
[30]
[21]
[15]
[42, 45]
[31, 0, 9]
[42]
[45]
[31]
[0, 9]
[0]
[9]
[0, 9, 15, 20, 21, 30, 31, 42, 45]

Hope this will help you to understand the logic.

This implementation was easy to understand from others, in C it was so easy to merge sort, but in python it was more than frustrating. — mSatyam, May 31 '17 at 21:01
Space complexity is still O(n), it's not an in-place Merge sort. [ref](https://en.wikipedia.org/wiki/Sorting_algorithm) — Kiran Kumar Kotari, Apr 17 '19 at 12:21

Merge Sort in place for python (Cant find what is wrong)

3 Answers3

Linked