title: Finding midpoint of array in MIPS - Merge sort
body: <p>I'm trying to create a merge sort algorithm in MIPS and I've identified a bug in my code. In my program, I'm keeping references to the start point and end point of my array (<code>$a0</code> and <code>$a1</code> respectively). I'm also keeping track of its length as <code>$a1 - $a0 + 4</code>. The problem is that I don't know how to calculate the midpoint of the array correctly. I need to do so for these equivalent function calls in C:</p>
  
  <pre><code>mergesort(a, start, mid);
  mergesort(a, mid + 1, end);
  </code></pre>
  
  <p>I'm new to MIPS so I'm not exactly sure how you do the arithmetic with 4-bit addresses. I can't add them as <code>($a0 + $a1)/2</code> since adding two addresses will cause overflow.</p>
  
  <p>My array is declared up on top as this:</p>
  
  <pre><code>array: .word 0:15
  </code></pre>
  
  <p>I can assume that not more than 15 numbers will be entered. <code>$s0</code> (the pointer to the start of the array), <code>$s1</code> (the pointer to the space AFTER the last element), <code>$a0</code> (the starting point argument), and <code>$a1</code> (the end point argument) are all stored like this:</p>
  
  <pre><code>la $s0, array
  move $s1, $s0 // $s1 increments by 4 each time an element is added
  ...
  move $a0, $s0
  addi $a1, $s1, -4 // subtract four because we want to refer to the last element
  </code></pre>
  
  <p>How can I calculate the mid index of that array given $a0 and $a1 as references? Any help would be appreciated. Thanks!</p>