title: Quick Sort algorithm not working for all arrays
body: <p>This is for a homework assignment. I will eventually be translating this code into MIPS assembly, but that is the easy part for me. I have been debugging this code for hours and hours and have been to my professors office hours, but I still cannot make my quick sort algorithm work. Here is the code along with a few of my comments about where I think the problem areas are:</p>
  
  <pre><code>// This struct is in my .h file
  typedef struct {
      // v0 points to the first element in the array equal to the pivot
      int *v0;
  
      // v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
      int *v1;
  } PartRet;
  
  void swap(int *a, int *b) {
      int temp = *a;
      *a = *b;
      *b = temp;
  }
  
  PartRet partition(int *lo, int *hi) {
      // Will later be translating this to MIPS where 2 values can be returned. I am using a PartRet struct to simulate this.
      PartRet retval;
  
      // We must use the last item as the pivot
      int pivot = *hi;
  
      int *left = lo;
  
      // Take the last value before the pivot
      int *right = hi - 1;
  
      while (left &lt; right) {
          while((left &lt; hi) &amp;&amp; (*left &lt;= pivot)) {
              ++left;
          }
  
          while((right &gt; lo) &amp;&amp; (*right &gt; pivot)) {
              --right;
          }
  
          if (left &lt; right) {
              swap(left++, right--);
          }
      }
  
      // Is this correct? left will always be &gt;= right after the while loop
      if (*hi &lt; *left) {
          swap(left, hi);
      }
  
      // MADE CHANGE HERE
      int *v0 = hi;
      int *v1;
  
      // Starting at the left pointer, find the beginning of the sub-array where the elements are equal to the pivot
      // MADE CHANGE HERE
      while (v0 &gt; lo &amp;&amp; *(v0 - 1) &gt;= pivot) {
          --v0;
      }
  
      v1 = v0;
  
      // Starting at the beginning of the sub-array where the elements are equal to the pivot, find the element after the end of this array.
      while (v1 &lt; hi &amp;&amp; *v1 == pivot) {
      ++v1;
      }
  
      if (v1 &lt;= v0) {
          v1 = hi + 1;
      }
  
      // Simulating returning two values
      retval.v0 = v0;
      retval.v1 = v1;
  
      return retval;
  }
  
  void quicksort(int *array, int length) {
      if (length &lt; 2) {
          return;
      }
  
      PartRet part = partition(array, array + length - 1);
  
      // I *think* this first call is correct, but I'm not sure.
      int firstHalfLength = (int)(part.v0 - array);
      quicksort(array, firstHalfLength);
  
      int *onePastEnd = array + length;
      int secondHalfLength = (int)(onePastEnd - part.v1);
  
      // I have a feeling that this isn't correct
      quicksort(part.v1, secondHalfLength);
  }
  </code></pre>
  
  <p>I have even tried rewriting the code using code samples online but the requirement is to use the lo and hi pointers but no code samples that I have found use this. When I debug the code I only end up making the code work for some arrays, not others, especially when the pivot is the smallest element in the array.</p>