Merge Sort not happening correctly - Python
<p>Sorting is not happening correctly. Can some one help on sorting with this approach. Also please let me know where I am going wrong. I am new to Python so I am doing this myself. I am using the usual approach as we do in C or other languages.</p>

<pre><code>base =[5,4,3,2,1]

def splitarray (low, high):
    if  low &lt; high:
        mid = (high+low)/2

        splitarray (low, mid)
        splitarray (mid+1,high)
        merge(low,mid,high)

    else:
        return

def merge(low,mid,high):
    print("merge " +str(low) + " - " +str(mid)+" - "+ str(high))
    result = [0]*len(base)
    k = 0
    i=low
    j=mid+1
    l=0


    while i &lt;= mid and j &lt;= high:
        if (base[i] &lt; base[j]):

            result[k]= base[i]
            k+=1
            i += 1

        if (base[i] &gt; base[j])  :


            result[k]= base[j]

            j += 1
            k += 1





    while i &lt;= mid:
        result[k]= base[i]
        k += 1
        i += 1
    while j &lt;= high:
        result[k]= base[j]
        #count = count + mid - i
        j += 1
        k += 1

    print result

    l = low
    k= 0
    while l &lt;= high:
        base[l] = result[l]
        l += 1


    print base
splitarray(0,len(base)-1)
</code></pre>

<p>Visually the way the algorithm operates is:<a href="http://i.stack.imgur.com/obJIB.png" rel="nofollow"><img src="http://i.stack.imgur.com/obJIB.png" alt="enter image description here"></a></p>

<p>So the most obvious way to implement merge sort is to return a new list for each merge. Maybe that can be optimized to what it seems like you're trying to do, which is to operate on a single top level <code>result</code>. But if you do it this way you can't just append to <code>result</code> at each level of merging. Because at the bottom level of the recursion you'll add four elements, then at the middle level you'll add four, then at the top level you'll add another four. It's too many. If you do it this way you should instead have a fixed <code>result</code> size and operate on its indices throughout the entire execution.</p>

<p>A second mistake is that you are reading through an unmodified <code>base</code> for every merge. The precondition at each merge step is that the two lists being merged are already sorted. If you're implementing the algorithm in the obvious way you can just use the return values from deeper merges. If you're implementing the algorithm in some optimized way using a top level <code>result</code>, then you should be reading from <code>result</code>, not <code>base</code>.</p>

python mergesort