title: Sort an array of integers into odd, then even
body: <p>I have a problem I found on an algorithm forum elsewhere.</p>
  
  <p>I have an array with random numbers (for example, <code>[5, 2, 7, 9, 2, 3, 8, 4]</code>) which should be returned to me sorted by odd then even. The order of the odds/evens is not important so in the example it would probably be <code>[5, 7, 9, 3, 2, 2, 8, 4]</code>.</p>
  
  <p>My first thought was to use a <code>.reduce()</code> function to just push them into two different arrays and then join them together, but there are some added complexities to this task.</p>
  
  <p>The added rules of the task are that the sort should maintain a constant extra space, and modify the array in place. It should also use an algorithm which scales consistently with the size of the array.</p>
  
  <p><strong>Which algorithm?</strong></p>
  
  <p>Judging by <a href="https://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms">Wikipedia's list</a>, there are a number of algorithms which scale consistently and use a constant amount of space. I also found <a href="https://mgechev.github.io/javascript-algorithms/sorting_bubblesort.js.html">this website</a> which has a nice bubble sort to use (also posted below), which seems stable and follows my rules <em>(I think?)</em>.</p>
  
  <p>I'm not sure if this is the right algorithm to use, or how to approach this part of the task at all.</p>
  
  <p><strong>Bubble:</strong></p>
  
  <pre><code>  function comparator(a, b) {
      return a - b;
    }
    /**
     * Bubble sort algorithm.&lt;br&gt;&lt;br&gt;
     * Complexity: O(N^2).
     *
     * @example
     * var sort = require('path-to-algorithms/src/' +
     * 'sorting/bubblesort').bubbleSort;
     * console.log(sort([2, 5, 1, 0, 4])); // [ 0, 1, 2, 4, 5 ]
     *
     * @public
     * @module sorting/bubblesort
     * @param {Array} array Input array.
     * @param {Function} cmp Optional. A function that defines an
     * alternative sort order. The function should return a negative,
     * zero, or positive value, depending on the arguments.
     * @return {Array} Sorted array.
     */
    function bubbleSort(array, cmp) {
      cmp = cmp || comparator;
      var temp;
      for (var i = 0; i &lt; array.length; i += 1) {
        for (var j = i; j &gt; 0; j -= 1) {
          if (cmp(array[j], array[j - 1]) &lt; 0) {
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
          }
        }
      }
      return array;
    }
  </code></pre>