title: Python Merge sort without slicing
body: <p>Ive attempted to write a quick sort implementation without using slicing but I'm running into problems with halfway through runtime - was wondering if anyone could show me where I'm going wrong</p>
  
  <p>I've added a few print statements (commented out) so you can see whats happening before and after each stage:</p>
  
  <pre><code>def mergesort(arr, l, r):
  
      #print('start: ', arr[l:r])
  
      if len(arr[l:r]) &lt;=1:
          return arr[l:r]
  
      mid = l + (r-l) // 2
      left    = mergesort(arr, l, mid)
      right   = mergesort(arr, mid, r)
  
      l_idx = l
      r_idx = mid
      final = []
  
      while l_idx &lt; mid and r_idx &lt; r:
          if arr[l_idx] &lt;= arr[r_idx]:
              final.append(arr[l_idx])
              l_idx+=1
          else:
              final.append(arr[r_idx]) 
              r_idx+=1
  
  
      for val in arr[l_idx:mid]:
          final.append(val)
  
      for val in arr[r_idx:r]:
          final.append(val)
  
      #print('final: ', final[l:r])
      #print()
      #print()
      return final 
  
  
  
      print(merge([0, 9, 3, 7, 4, 2, 6, 1], 0, 8))
  </code></pre>
  
  <p>The values I'm getting show that for the left had side it works well but for the right it doesn't. which is curious because it seems to work for the right hand side of the left...</p>
  
  <p>The stdout is:</p>
  
  <pre><code>start:  [0, 9, 3, 7, 4, 2, 6, 1]
  start:  [0, 9, 3, 7]
  start:  [0, 9]
  start:  [0]
  start:  [9]
  final:  [0, 9]
  
  
  start:  [3, 7]
  start:  [3]
  start:  [7]
  final:  []
  
  
  final:  [0, 3, 7, 9]
  
  
  start:  [4, 2, 6, 1]
  start:  [4, 2]
  start:  [4]
  start:  [2]
  final:  []
  
  
  start:  [6, 1]
  start:  [6]
  start:  [1]
  final:  []
  
  
  final:  []
  
  
  final:  [0, 4, 2, 6, 1, 9, 3, 7]
  </code></pre>