title: How to sort an array in linear timer and in place?
body: <p><a href="http://www.programminginterview.com/content/arrays" rel="nofollow noreferrer" title="Question Origin">question origin</a></p>
  
  <p>Given an unsorted array of size n containing objects with ids of 0 … n-1, sort the array in place and in linear time. Assume that the objects contain large members such as binary data, so instantiating new copies of the objects is prohibitively expensive.</p>
  
  <pre><code>void linearSort(int* input, const int n) {
      for (int i = 0; i &lt; n; i++) {
          while (input[i] != i) {
              // swap
              int swapPoint = input[i];
              input[i] = input[swapPoint];
              input[swapPoint] = swapPoint;
          }
      }
  }
  </code></pre>
  
  <p>Is this linear? Does this sort work with any kind of array of ints? If so, why do we need quicksort anymore?</p>