How is the final array constructed in this Ruby quicksort implementation?
<p>I'm learning some soring algorithms in Ruby, and learned this recursive implementation of quicksort:</p>

<pre><code>class Array
  def quicksort
    return [] if empty?

    pivot = delete_at(rand(size))

    left, right = partition(&amp;pivot.method(:&gt;))

    return *left.quicksort, pivot, *right.quicksort
  end
end

array = [5,3,2,18,1,6,4,7,5,9,0]
p array
#=&gt; [5, 3, 2, 18, 1, 6, 4, 7, 5, 9, 0]

p array.quicksort
#=&gt; [0, 1, 2, 3, 4, 5, 5, 6, 7, 9, 18]
</code></pre>

<p>I think I understand basically what's happening here. Do I have this right?</p>

<p>Chose an arbitrary pivot, store the number and delete that index from the array. Then partition the array, putting numbers <code>&gt; pivot</code> in an array <code>left</code>, and the numbers <code>&lt; pivot</code> in <code>right</code>. <code>Return pivot</code> and call quicksort recursively on <code>left</code> and <code>right</code> arrays if they have anything in them. </p>

<p>What I don't understand is how the final array is constructed; I don't see where the returned numbers are assigned the appropriate index. Does it happen when <code>pivot</code> is returned? How does it end up in the right index?</p>

<p>I think some of my confusion is coming from a lack of understanding about recursion. </p>

<p>Thanks in advance for any help.</p>