title: How to sort a List<String> in descending order as fast as possible
body: <p>I am trying to find a way to sort a List as fast as possible. I know about "bucket sort" which I will use(I think?). But before doing that. I think I am looking for the fastest possible clean algorithm first, - and then use that in bucket sort?</p>
  
  <p>The strings looks like below where I add 100.000 elements in a loop:</p>
  
  <pre><code>-0,awb/aje - ddfas/asa - asoo/qwa
  -1,awb/aje - ddfas/asa - asoo/qwa
  -2,awb/aje - ddfas/asa - asoo/qwa
  </code></pre>
  
  <p>So I want to sort in a descending order for the first comma delimited argument which is a double like: -0, -1, -2 etc..</p>
  
  <p>I have tried 3 Approaches where only the Approach 1 actually sorts correctly. Approach 2 and 3 do not sort entirely correctly in a descending order numeric wise.</p>
  
  <p>So the approach 1 which sorts correctly do this in 30 seconds. 
  The thing is that I will have about 3 Million elements and not only 100.000 like in this example which then should take at least 900 seconds or more.</p>
  
  <p>My question is how can we sort 100.000 or more correctly 3 million elements as fast as possible?
  <strong>Running: sortingtestBENCHMARKS() will show the results</strong></p>
  
  <pre><code>    public void sortingtestBENCHMARKS()
      {
          List&lt;String&gt; dataLIST = new List&lt;String&gt;(); List&lt;String&gt; sortedLIST = new List&lt;String&gt;(); String resultString = ""; int index = 0;
          DateTime starttime = DateTime.Now; DateTime endtime = DateTime.Now; TimeSpan span = new TimeSpan();
          for (double i = 0; i &lt; 100000; i+=1)
          {
              dataLIST.Add("-" + i + "," + "awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
          }
          dataLIST = shuffle(dataLIST);
  
          /*--------------------------------------------------------------------------*/
          //APPROACH 1: 30 seconds (Sorts correctly in descending order)
          starttime = DateTime.Now;
          dataLIST = sortLIST(dataLIST);
          endtime = DateTime.Now;
          span = endtime - starttime;
          resultString = "Approach 1: " + span.TotalSeconds;
          dataLIST = shuffle(dataLIST);
  
          /*--------------------------------------------------------------------------*/
          //APPROACH 2: 55 seconds (Sorts INcorrectly in descending order)
          starttime = DateTime.Now;
          for (int i = 0; i &lt; dataLIST.Count; i++) 
          {
              index = sortedLIST.BinarySearch(dataLIST[i]);
              if (index &lt; 0)
              {
                  sortedLIST.Insert(~index, dataLIST[i]);
              }
          }
          endtime = DateTime.Now;
          span = endtime - starttime;
          resultString = resultString + "\nApproach 2: " + span.TotalSeconds;
  
          /*--------------------------------------------------------------------------*/
          //APPROACH 3: 2 seconds (Sorts INcorrectly in descending order)
          starttime = DateTime.Now;
          dataLIST.Sort(); //1.6 seconds
          endtime = DateTime.Now;
          span = endtime - starttime;
          resultString = resultString + "\nApproach 3: " + span.TotalSeconds;
  
          /*--------------------------------------------------------------------------*/
  
          MessageBox.Show("Elapsed Times:\n\n" + resultString);
      }
      List&lt;String&gt; sortLIST(List&lt;String&gt; theLIST)
      {
          System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US");
          theLIST.Sort(new Comparison&lt;String&gt;((a, b) =&gt;
          {
              int result = 0;
              double ad = 0;
              double bd = 0;
              NumberFormatInfo provider = new NumberFormatInfo();
              provider.NumberGroupSeparator = ",";
              provider.NumberDecimalSeparator = ".";
              provider.NumberGroupSizes = new int[] { 5 };
              ad = Convert.ToDouble(a.Replace("a", "").Replace("c", "").Split(',')[0], provider);
              bd = Convert.ToDouble(b.Replace("a", "").Replace("c", "").Split(',')[0], provider);
              if (ad &lt; bd)
              {
                  result = 1;
              }
              else if (ad &gt; bd)
              {
                  result = -1;
              }
              return result;
          }));
          return theLIST;
      }
      List&lt;String&gt; shuffle(List&lt;String&gt; list)
      {
          var randomizedList = new List&lt;String&gt;();
          var rnd = new Random();
          while (list.Count != 0)
          {
              var index = rnd.Next(0, list.Count);
              randomizedList.Add(list[index]);
              list.RemoveAt(index);
          }
          return randomizedList;
      }
  </code></pre>