Bottom Up MergeSort using Python
<p>I've spent countless hours trying to do this. Could anyone point out my mistake?</p>

<p><code>a</code> is just a list, <code>tmp</code> is an empty list of size <code>len(a)</code></p>

<p><code>z</code> is basically <code>len(a)</code> </p>

<p><code>
a = [6,5,4,3,2,1]
print 'unsorted:',a
z = len(a)
tmp = range(len(a))
</code></p>

<p>Here's my sort function:</p>

<pre><code>def sort(a,tmp):
        width=1
        while(width&lt;z):
                p=0
                while(p&lt;z):
                        left =p
                        middle = p+width
                        right = p+2*width
                        merge(a,left,middle,right,tmp)
                        p = p+2*width
                t=0        
                while(t&lt;z):
                    a[t]=tmp[t]
                    t=t+1
                width=width*2
                print '\n'
</code></pre>

<p>and here's merge function :</p>

<pre><code>def merge(a,iLeft,iMiddle,iRight,tmp):
        i = iLeft
        j = iMiddle
        k = iLeft
        print iLeft,iMiddle,iRight,'[',i,j,k,']'
        #print i ,j, k,'\n\n'

        while(i&lt;iMiddle or j&lt;iRight):
                if(i&lt;iMiddle and j&lt;iRight):
                        if(a[i]&lt;a[j]):
                                tmp[k]=a[i]
                                i += 1
                                k += 1
                        else:
                                tmp[k]=a[j]
                                j += 1
                                k += 1

                elif (i==iMiddle):
                        tmp[k] = a[j]
                        j += 1
                        k += 1
                elif (j==iRight):
                        tmp[k]= a[i]
                        i += 1
                        k += 1
</code></pre>

<p>[This Visualization] might help. I still don't know why it's acting this way. </p>

<p>I'm not sure where I am going wrong? Is it the indentation or the looping?</p>

<pre><code>Output ::
unsorted: [6, 5, 4, 3, 2, 1]
0 1 2 [ 0 1 0 ]
2 3 4 [ 2 3 2 ]
4 5 6 [ 4 5 4 ]


0 2 4 [ 0 2 0 ]
4 6 8 [ 4 6 4 ]
Traceback (most recent call last):
  File "BUmer.py", line 45, in &lt;module&gt;
    sort(a,tmp)
  File "BUmer.py", line 14, in sort
    merge(a,left,middle,right,tmp)
  File "BUmer.py", line 27, in merge
    if(a[i]&lt;a[j]):
IndexError: list index out of range
</code></pre>

<p><a href="http://www.pythontutor.com/visualize.html#code=a+%3D+%5B6,8,33,21,9,8%5D%0Aprint+%27unsorted%3A%27,a%0Az+%3D+len(a%29%0Atmp+%3D+range(len(a%29%29%0Adef+sort(a,tmp%29%3A%0A++++++++width%3D1%0A++++++++while(width%3Cz%29%3A%0A++++++++++++++++p%3D0%0A++++++++++++++++while(p%3Cz%29%3A%0A++++++++++++++++++++++++left+%3Dp%0A++++++++++++++++++++++++middle+%3D+p%2Bwidth%0A++++++++++++++++++++++++right+%3D+p%2B2*width%0A++++++++++++++++++++++++merge(a,left,middle,right,tmp%29%0A++++++++++++++++++++++++p+%3D+p%2B2*width%0A++++++++++++++++t%3D0++++++++%0A++++++++++++++++while(t%3Cz%29%3A%0A++++++++++++++++++++a%5Bt%5D%3Dtmp%5Bt%5D%0A++++++++++++++++++++t%3Dt%2B1%0A++++++++++++++++width%3Dwidth*2%0A++++++++++++++++print+%27%5Cn%27%0Adef+merge(a,iLeft,iMiddle,iRight,tmp%29%3A%0A++++++++i+%3D+iLeft%0A++++++++j+%3D+iMiddle%0A++++++++k+%3D+iLeft%0A++++++++print+iLeft,iMiddle,iRight,%27%5B%27,i,j,k,%27%5D%27%0A++++++++%23print+i+,j,+k,%27%5Cn%5Cn%27%0A+%0A++++++++while(i%3CiMiddle+or+j%3CiRight%29%3A%0A++++++++++++++++if(i%3CiMiddle+and+j%3CiRight%29%3A%0A++++++++++++++++++++++++if(a%5Bi%5D%3Ca%5Bj%5D%29%3A%0A++++++++++++++++++++++++++++++++tmp%5Bk%5D%3Da%5Bi%5D%0A++++++++++++++++++++++++++++++++i+%2B%3D+1%0A++++++++++++++++++++++++++++++++k+%2B%3D+1%0A++++++++++++++++++++++++else%3A%0A++++++++++++++++++++++++++++++++tmp%5Bk%5D%3Da%5Bj%5D%0A++++++++++++++++++++++++++++++++j+%2B%3D+1%0A++++++++++++++++++++++++++++++++k+%2B%3D+1%0A+%0A++++++++++++++++elif+(i%3D%3DiMiddle%29%3A%0A++++++++++++++++++++++++tmp%5Bk%5D+%3D+a%5Bj%5D%0A++++++++++++++++++++++++j+%2B%3D+1%0A++++++++++++++++++++++++k+%2B%3D+1%0A++++++++++++++++elif+(j%3D%3DiRight%29%3A%0A++++++++++++++++++++++++tmp%5Bk%5D%3D+a%5Bi%5D%0A++++++++++++++++++++++++i+%2B%3D+1%0A++++++++++++++++++++++++k+%2B%3D+1%0A+%0Asort(a,tmp%29%0Aprint+%27Sorted+Array%3A%27,a&amp;mode=display&amp;origin=opt-frontend.js&amp;cumulative=false&amp;heapPrimitives=false&amp;textReferences=false&amp;py=2&amp;rawInputLstJSON=%5B%5D&amp;curInstr=0" rel="nofollow"> This visualization</a> may help. I still don't know why this is happening. </p>