<p dir="auto">Is sortrows() running as fast as it should?  I have no deep knowledge of the theoretical performance possibilities for a "sortrows()" algorithm vs. a traditional vector sort algorithm, but I'm finding that lexicographically sorting an N-by-2 matrix is MUCH slower than sorting an N-by-1 vector.</p>
<p dir="auto">For example, on my machine, sorting a random vector of 20 million Float64s takes about 2 seconds.  Sorting a 20 million by 2 matrix, using sortrows(), takes about 250 seconds.</p>
<p dir="auto">Is there any reason why lexicographic sorting should not have N * log(N) performance?  If its N * log(N), then sortrows() should take only about 2 * log(2) more time than sort() on a vector.</p>
<p dir="auto">For what its worth, <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/users/time/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="https://github.com/time">@time</a> reports that a meaningful chunk of the running time (10%) is garbage collection .</p>
<p dir="auto">For reference, here's my versioninfo()<br>
julia&gt; versioninfo()<br>
Julia Version 0.3.4<br>
Commit <a class="commit-link" data-hovercard-type="commit" data-hovercard-url="https://github.com/JuliaLang/julia/commit/33920266908e950936ef3f8503810a2d47333741/hovercard" href="https://github.com/JuliaLang/julia/commit/33920266908e950936ef3f8503810a2d47333741"><tt>3392026</tt></a>* (2014-12-26 10:42 UTC)<br>
Platform Info:<br>
System: Linux (x86_64-redhat-linux)<br>
CPU: Intel(R) Xeon(R) CPU E7-8891 v2 @ 3.20GHz<br>
WORD_SIZE: 64<br>
BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)<br>
LAPACK: libopenblas<br>
LIBM: libopenlibm<br>
LLVM: libLLVM-3.3</p>
<p dir="auto">Julia  sorting functions are slow compared to Matlab.</p>
<hr>
<h4 dir="auto">Outdated begin</h4>
<p dir="auto"><del>Matlab R2012b sorting of integer arrays:</del></p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="&gt;&gt; a=randi(30000000,30000000,2);
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.882043 seconds.
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.903528 seconds.
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.900367 seconds.
``

Julia sorting of integer arrays:
julia&gt; a=rand(Int64,30000000,2);

julia&gt; @time sort(a,2);
elapsed time: 46.625749977 seconds (17279978752 bytes allocated, 19.15% gc time)"><pre class="notranslate"><code class="notranslate">&gt;&gt; a=randi(30000000,30000000,2);
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.882043 seconds.
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.903528 seconds.
&gt;&gt; tic; b=sort(a,2); toc
Elapsed time is 0.900367 seconds.
``

Julia sorting of integer arrays:
julia&gt; a=rand(Int64,30000000,2);

julia&gt; @time sort(a,2);
elapsed time: 46.625749977 seconds (17279978752 bytes allocated, 19.15% gc time)
</code></pre></div>
<p dir="auto"><del>The Julia sort() is more than 40 times slower than Matlab.</del></p>
<h4 dir="auto">Outdated end</h4>
<hr>
<p dir="auto">The sortslices(a; dims=1) has a similar problem.  Still working with the same 30,000,000 x 2 array size:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="&gt;&gt;  a=rand(Int64,30000000,2);
&gt;&gt; tic; c=sortrows(a); toc
Elapsed time is 12.071053 seconds."><pre class="notranslate"><code class="notranslate">&gt;&gt;  a=rand(Int64,30000000,2);
&gt;&gt; tic; c=sortrows(a); toc
Elapsed time is 12.071053 seconds.
</code></pre></div>
<p dir="auto">Compare with</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="julia&gt; @time sortslices(a; dims=1);
100.747272 seconds (31.13 M allocations: 2.737 GiB, 1.78% gc time)"><pre class="notranslate"><code class="notranslate">julia&gt; @time sortslices(a; dims=1);
100.747272 seconds (31.13 M allocations: 2.737 GiB, 1.78% gc time)
</code></pre></div>