# How do I sort an integer array while also keeping identical elements apart from each other?

John Feminella
Feb 02, 2015
<p>This isn't really a "sort", per se. There's a sorting <em>step</em>, but ultimately what you're really trying to do is called a <a href="http://en.wikipedia.org/wiki/Transpose" rel="nofollow"><strong>matrix transposition</strong></a>.</p> <p>Two ways of accomplishing that are below.</p> <h1>More verbosely</h1> <p>The first way is longer and is broken down into more steps for clarity (hopefully).</p> <p>First, we'll sort and group the related array elements together:</p> <pre><code>v = arr.sort.group_by { |e| e }.values # =&gt; [[38, 38], [40, 40, 40], [41, 41, 41, 41], [60]] </code></pre> <p>Let's make a new array for the result:</p> <pre><code>r = [] </code></pre> <p>Now we'll get the one with the largest number of elements:</p> <pre><code>max = arr.map { |e| arr.count(e) }.max </code></pre> <p>Then we'll loop through the array that many times,</p> <pre><code>max.times { ... } </code></pre> <p>pulling one element from each subarray each time, then putting it onto the result array:</p> <pre><code>max.times { v.each { |a| r &lt;&lt; a.shift } }; r.compact! </code></pre> <p>and we have our answer:</p> <pre><code># =&gt; [38, 40, 41, 60, 38, 40, 41, 40, 41, 41] </code></pre> <h1>More concisely</h1> <p>Now that you've seen the long way, here's a more concise approach. This doesn't require as much iteration (or an output array!).</p> <p>First, we fill the subarrays to a size of <code>max</code>:</p> <pre><code>arr.sort. group_by { |e| e }.values. map { |a| a.fill(nil, a.size..max-1) } # ... </code></pre> <p>This is now a square array of size <code>max</code> by <code>max</code> elements, so we can treat it as a square matrix. That means we can transpose the elements so that the "rows" become the "columns", and vice versa.</p> <p>So we'll <code>transpose</code>, then <code>flatten</code> to get a single array, then <code>compact</code> to get rid of the <code>nil</code> elements:</p> <pre><code># ... (...).transpose.flatten.compact </code></pre> <p>and we get the desired result:</p> <pre><code># =&gt; [38, 40, 41, 60, 38, 40, 41, 40, 41, 41] </code></pre> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/28126732/How%20do%20I%20sort%20an%20integer%20array%20while%20also%20keeping%20identical%20elements%20apart%20from%20each%20other?/28127203">Stack Overflow</a>.</p>