title: How can I make a bottom-up mergesort function that mutates the input list?
body: <p>I am trying to implement a bottom-up mergesort in Python along the lines of the second example on this Wikipedia page (said to be written in “C-like code”):</p>
  
  <p><a href="https://en.m.wikipedia.org/wiki/Merge_sort" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Merge_sort</a></p>
  
  <p>I have created a script that works, but when I try to encapsulate it in a function, that function fails to mutate the input list. Mutating the input list <strong>is</strong> what I want it to do.</p>
  
  <p>Does anybody know why my function BottomUpMergeSort cannot alter the input list? I am aware that nested while loops are not recommended, but the first script seems to work fine. Many thanks in advance.</p>
  
  <p>My first script, which mutates list A:</p>
  
  <pre class="lang-py prettyprint-override"><code>import random
  
  A = list(range(10))
  random.shuffle(A)
  
  def Merge(a, b, start, mid, end):
      i = start
      j = mid
      for k in range(start, end):
          if i &lt; mid and (j &gt;= end or a[i] &lt;= a[j]):
              b[k] = a[i]
              i += 1
          else:
              b[k] = a[j]
              j += 1
  
  print(f'A: {A}')
  # 'A: [3, 4, 5, 1, 8, 7, 2, 9, 0, 6]'
  
  n = len(A)
  B = A[:]
  width = 1
  while width &lt; n:
      start = 0
      while start &lt; n:
          mid = min(n, start + width)
          end = min(n, start + (2 * width))
          Merge(A, B, start, mid, end)
          start += 2 * width
      A = B[:]
      width *= 2
  
  print(f'A: {A}')
  # 'A: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]'
  </code></pre>
  
  <p>My second script, which does not mutate list A:</p>
  
  <pre class="lang-py prettyprint-override"><code>import random
  
  A = list(range(10))
  random.shuffle(A)
  
  def Merge(a, b, start, mid, end):
      i = start
      j = mid
      for k in range(start, end):
          if i &lt; mid and (j &gt;= end or a[i] &lt;= a[j]):
              b[k] = a[i]
              i += 1
          else:
              b[k] = a[j]
              j += 1
  
  print(f'A: {A}')
  # 'A: [1, 9, 5, 3, 4, 8, 7, 6, 0, 2]'
  
  def BottomUpMergeSort(a):
      n = len(a)
      b = a[:]
      width = 1
      while width &lt; n:
          start = 0
          while start &lt; n:
              mid = min(n, start + width)
              end = min(n, start + (2 * width))
              Merge(a, b, start, mid, end)
              start += 2 * width
          a = b[:]
          width *= 2
  
  BottomUpMergeSort(A)
  
  print(f'A: {A}')
  # 'A: [1, 9, 5, 3, 4, 8, 7, 6, 0, 2]'
  </code></pre>
  
  <p>As you can see, the first script changes A, while the second does not.</p>