title: Fastest way to sort an array only using these blackbox functions?
body: <p>The problem goes as follows:</p>
  <blockquote>
  <p>As input you get an array (<em>ARR</em>) of size <em>N</em> that you do not know the contents of – and will not be able to see the contents of – and a pre-assigned value <em>U≪N</em>. Your solution should work for any value of <em>U</em> and <em>N</em>.</p>
  <p>You are given a work array (<em>W</em>) of size <em>N</em>. You can also use the following helper functions which both run in <em>O(1)</em> time:</p>
  <ul>
  <li><p><em>SORT(A, B): SORT</em> will take two contiguous sections of the array <em>ARR</em> or <em>W</em>, of size <em>|A|≤U</em> and <em>|B|≤U</em>, merge them into a new array, sort them, then put the lower part of size <em>|A|</em> of this new array back into <em>A</em>, and the remaining values into <em>B</em>. It will return the number of values from <em>A</em> that remained in <em>A</em>.</p>
  </li>
  <li><p><em>COPY(A -&gt; C): COPY</em> will make a copy of the contents of <em>A</em> into <em>C</em>. <em>|A| == |C|</em>.</p>
  </li>
  </ul>
  </blockquote>
  <p>I already have a solution to this problem, which is a variant on merge sort and has a similar runtime of <em>O( (N/U) log (N/U) )</em>, but I was wondering if there was a faster solution.</p>
  <p>Also, I was wondering how you could sort the array under the constraint that you no longer have the work array (<em>W</em>).</p>
  <hr />
  <p>As requested, my solution (very informal and simplified)</p>
  <pre class="lang-py prettyprint-override"><code># Define helper subroutine MERGE (merges two sorted arrays)
  MERGE (array A[1...m], array B[1...n]):
    a_idx = 1
    b_idx = 1
    w_idx = 1
    while a_idx &lt; m+1 and b_idx &lt; n+1; do
      COPY( A[a_idx ... a_idx+U], W[w_idx ... w_idx+U])
      COPY( B[b_idx ... b_idx+U], W[w_idx+U+1 ... w_idx+2U])
      F=W[w_idx ... w_idx+U]
      G=W[w_idx+U+1 ... w_idx+2U]
      offset = SORT(F,G)
      a_idx += offset
      b_idx += (U-offset)
      w_idx += U
    end while
  
    if a_idx != m+1:
      # this can be done in a while loop as well but just writing it down like this for simplification
      COPY( A[a_idx ... m+1], W[w_idx ... w_idx+(m+1-a_idx)])
      w_idx += (m+1-a_idx)
    end if
  
    if b_idx != n+1:
      # this can be done in a while loop as well but just writing it down like this for simplification
      COPY( B[b_idx ... n+1], W[w_idx ... w_idx+(n+1-b_idx)])
      w_idx += (n+1-b_idx)
    end if
    
    COPY(W[1 ... m], A[1 ... m])
    COPY(W[m+1 ... m+n], B[1 ... n])
  end MERGE
  </code></pre>
  <p>Once you have this subroutine, you can easily sort the original array into sorted pieces of size <em>2U</em> using <em>SORT</em>, and then use merge sort logic with this routine to merge it into one whole sorted array.</p>