title: How does my randomly partitioned array look in the general case?
body: <ol>
  <li>I have an array of n random integers</li>
  <li>I choose a random integer and partition by the chosen random integer (all integers smaller than the chosen integer will be on the left side, all bigger integers will be on the right side)</li>
  </ol>
  <p>What will be the size of my left and right side in the average case, if we assume no duplicates in the array?</p>
  <p>I can easily see, that there is 1/n chance that the array is split in half, if we are lucky. Additionally, there is 1/n chance, that the array is split so that the left side is of length 1/2-1 and the right side is of length 1/2+1 and so on.</p>
  <p>Could we derive from this observation the &quot;average&quot; case?</p>