title: Mathematica how to efficiently find the minimum value using an ordering function
body: <p>I have the following list of pairs of data:</p>
  
  <pre><code>pairs = {{3, "John"}, {1, "Bob"}, {2, "Jane"}, {1, "Beth"}};
  </code></pre>
  
  <p>I would like to find the pair of data with the minimum first value.  In the example above the pair I am looking for is: <code>{1, "Bob"}</code> or <code>{1, "Beth"}</code>, but not both of them.</p>
  
  <p>I can use <code>Sort[pairs, #1[[1]] &lt; #2[[1]] &amp;][[1]]</code> to accomplish this. However, since even the fastest sorts having a big O > O(n), it leads me to think there has to be a more efficient way to do this.</p>
  
  <p>The following gives me the correct answer:</p>
  
  <pre><code>minPair = pairs[[1]];
  Map[Function[x, If[x[[1]] &lt; minPair[[1]], minPair = x]], pairs];
  minPair;
  </code></pre>
  
  <p>but, it is slower than using <code>Sort</code> above. I know, my Mathematica-fu is just not there yet, hence my question.</p>
  
  <h2>Timings</h2>
  
  <pre><code>SetAttributes[TimingDo, HoldRest];
  TimingDo[note_String, func_] := 
    results = 
     Append[results, {note , func, Timing[Do[func, {iterations}]][[1]]}];
  
  pairs = {{3, "John"}, {1, "Bob "}, {2, "Jane"}, {1, "Beth"}};
  results = {};
  iterations = 10000;
  
  TimingDo[ "mmorris[Sort]:               ",
    Sort[pairs, #1[[1]] &lt; #2[[1]] &amp;][[1]]];
  
  TimingDo["mmorris[Map]:                ",
    minPair = pairs[[1]];
    Map[Function[x, If[x[[1]] &lt; minPair[[1]], minPair = x;]], pairs];
    minPair];
  
  TimingDo["mmorris[Map2]:               ",
    minPair = pairs[[1]];
    minValue = minPair[[1]];
    Map[Function[x, 
      If[x[[1]] &lt; minValue, minPair = x; minValue = minPair[[1]];]], 
     pairs];
    minPair];
  
  TimingDo["Mike Honeychurch[Position]:  ",
    pairs[[Position[pairs, Min[pairs[[All, 1]]]][[1, 1]]]]];
  
  TimingDo["Mike Honeychurch[Ordering]:  ",
    pairs[[First@Ordering[pairs[[All, 1]]]]]];
  
  TimingDo["Mike Honeychurch[Ordering']: ",
    pairs[[First@Ordering[pairs[[All, 1]], 1]]]];
  
  TimingDo["Mike Honeychurch[SortBy]:    ",
    SortBy[pairs, First][[1]]];
  
  cf = Compile[{{in, _Integer, 1}}, Block[{x, pos}, x = Part[in, 1];
      pos = 0;
      Do[If[Part[in, i] &lt; x, x = Part[in, i];
         pos = i;];, {i, Length[in]}];
      pos]];
  
  TimingDo["ruebenko[Compile]:           ",
    {p1, p2} = Developer`ToPackedArray /@ Transpose[pairs];
    pairs[[cf[p1]]]];
  
  TimingDo[ "ruebenko[Ordering]:          ",
    {p1, p2} = Developer`ToPackedArray /@ Transpose[pairs];
    pairs[[Ordering[p1][[1]]]]];
  
  TimingDo["TomD[Select]:                ",
    Select[pairs, #[[1]] == Min[pairs[[All, 1]]] &amp;, 1][[1]]];
  
  TimingDo["TomD[Function]:              ",
    (Function[xx, Select[xx, #[[1]] == Min[xx[[All, 1]]] &amp;, 1]]@
       pairs)[[1]]];
  
  Map[Print, Sort[results, #1[[3]] &lt; #2[[3]] &amp;]];
  </code></pre>
  
  <h2>Results (List size of 4)</h2>
  
  <p><code>pairs = {{3, "John"}, {1, "Bob "}, {2, "Jane"}, {1, "Beth"}};</code></p>
  
  <pre><code>{Mike Honeychurch[Ordering']: ,{1,Bob },0.01381}
  
  {Mike Honeychurch[Ordering]:  ,{1,Bob },0.016171}
  
  {Mike Honeychurch[SortBy]:    ,{1,Beth},0.036649}
  
  {TomD[Select]:                ,{1,Bob },0.042448}
  
  {Mike Honeychurch[Position]:  ,{1,Bob },0.042909}
  
  {ruebenko[Ordering]:          ,{1,Bob },0.048088}
  
  {ruebenko[Compile]:           ,{1,Bob },0.050277}
  
  {TomD[Function]:              ,{1,Bob },0.054296}
  
  {mmorris[Sort]:               ,{1,Beth},0.06838}
  
  {mmorris[Map2]:               ,{1,Bob },0.117905}
  
  {mmorris[Map]:                ,{1,Bob },0.119051}
  </code></pre>
  
  <h2>Results (List size of 1000)</h2>
  
  <p><code>pairs = RandomInteger[1000, {1000, 2}];</code></p>
  
  <pre><code>{Mike Honeychurch[Ordering']: ,{0,217},0.236041}
  
  {ruebenko[Compile]:           ,{0,217},0.416627}
  
  {ruebenko[Ordering]:          ,{0,217},0.675427}
  
  {Mike Honeychurch[Ordering]:  ,{0,217},0.771243}
  
  {Mike Honeychurch[SortBy]:    ,{0,217},2.68054}
  
  {Mike Honeychurch[Position]:  ,{0,217},2.70455}
  
  {mmorris[Map2]:               ,{0,217},26.7715}
  
  {mmorris[Map]:                ,{0,217},29.8413}
  
  {mmorris[Sort]:               ,{0,217},98.1023}
  
  {TomD[Function]:              ,{0,217},115.968}
  
  {TomD[Select]:                ,{0,217},116.78}
  </code></pre>