C Sort and OrderBy comparison

Question

I can sort a list  using Sort or OrderBy  Which one is faster  Are both working on same  algorithm   List lt Person gt  persons   new List lt Person gt     persons Add new Person  P005    Janson     persons Add new Person  P002    Aravind     persons Add new Person  P007    Kazhal       1   persons Sort  p1 p2   gt string Compare p1 Name p2 Name true      2   var query   persons OrderBy n   gt  n Name  new NameComparer      class NameComparer   IComparer lt string gt        public int Compare string x string y              return  string Compare x  y  true

User · Answer

In a nutshell     List Array Sort       Unstable sort  Done in-place  Use Introsort Quicksort   Custom comparison is done by providing a comparer  If comparison is expensive  it might be slower than OrderBy    which allow to use keys  see below     OrderBy ThenBy       Stable sort  Not in-place   Use Quicksort  Quicksort is not a stable sort  Here is the trick   when sorting  if two elements have equal key  it compares their initial order  which has been stored before sorting    Allows to use keys  using lambdas  to sort elements on their values  eg   x   gt  x Id   All keys are extracted first before sorting  This might result in better performance than using Sort   and a custom comparer     Sources  MDSN  reference source and dotnet coreclr repository  GitHub     Some of the statements listed above are based on current  NET framework implementation  4 7 2   It might change in the future

User · Answer

Why not measure it   class Program       class NameComparer   IComparer lt string gt                public int Compare string x  string y                        return string Compare x  y  true                        class Person               public Person string id  string name                        Id   id              Name   name                    public string Id   get  set            public string Name   get  set               static void Main                 List lt Person gt  persons   new List lt Person gt             persons Add new Person  P005    Janson             persons Add new Person  P002    Aravind             persons Add new Person  P007    Kazhal              Sort persons           OrderBy persons            const int COUNT   1000000          Stopwatch watch   Stopwatch StartNew            for  int i   0  i  lt  COUNT  i                          Sort persons                     watch Stop            Console WriteLine  Sort   0 ms   watch ElapsedMilliseconds            watch   Stopwatch StartNew            for  int i   0  i  lt  COUNT  i                          OrderBy persons                     watch Stop            Console WriteLine  OrderBy   0 ms   watch ElapsedMilliseconds              static void Sort List lt Person gt  list                list Sort  p1  p2    gt  string Compare p1 Name  p2 Name  true               static void OrderBy List lt Person gt  list                var result   list OrderBy n   gt  n Name  new NameComparer    ToArray              On my computer when compiled in Release mode this program prints   Sort  1162ms OrderBy  1269ms     UPDATE   As suggested by  Stefan here are the results of sorting a big list fewer times   List lt Person gt  persons   new List lt Person gt     for  int i   0  i  lt  100000  i          persons Add new Person  P    i ToString     Janson    i ToString         Sort persons   OrderBy persons    const int COUNT   30  Stopwatch watch   Stopwatch StartNew    for  int i   0  i  lt  COUNT  i          Sort persons     watch Stop    Console WriteLine  Sort   0 ms   watch ElapsedMilliseconds    watch   Stopwatch StartNew    for  int i   0  i  lt  COUNT  i          OrderBy persons     watch Stop    Console WriteLine  OrderBy   0 ms   watch ElapsedMilliseconds     Prints   Sort  8965ms OrderBy  8460ms   In this scenario it looks like OrderBy performs better     UPDATE2   And using random names   List lt Person gt  persons   new List lt Person gt     for  int i   0  i  lt  100000  i          persons Add new Person  P    i ToString    RandomString 5  true         Where   private static Random randomSeed   new Random    public static string RandomString int size  bool lowerCase        var sb   new StringBuilder size       int start    lowerCase    97   65      for  int i   0  i  lt  size  i                  sb Append  char  26   randomSeed NextDouble     start              return sb ToString        Yields   Sort  8968ms OrderBy  8728ms   Still OrderBy is faster

User · Answer

Darin Dimitrov s answer shows that OrderBy is slightly faster than List Sort when faced with already-sorted input   I modified his code so it repeatedly sorts the unsorted data  and OrderBy is in most cases slightly slower   Furthermore  the OrderBy test uses ToArray to force enumeration of the Linq enumerator  but that obviously returns a type  Person    which is different from the input type  List lt Person gt     I therefore re-ran the test using ToList rather than ToArray and got an even bigger difference   Sort  25175ms OrderBy  30259ms OrderByWithToList  31458ms   The code   using System  using System Collections Generic  using System Diagnostics  using System Linq  using System Text   class Program       class NameComparer   IComparer lt string gt                public int Compare string x  string y                        return string Compare x  y  true                        class Person               public Person string id  string name                        Id   id              Name   name                    public string Id   get  set            public string Name   get  set            public override string ToString                         return Id          Name                       private static Random randomSeed   new Random        public static string RandomString int size  bool lowerCase                var sb   new StringBuilder size           int start    lowerCase    97   65          for  int i   0  i  lt  size  i                          sb Append  char  26   randomSeed NextDouble     start                      return sb ToString               private class PersonList   List lt Person gt                public PersonList IEnumerable lt Person gt  persons               base persons                               public PersonList                                public override string ToString                         var names   Math Min Count  5               var builder   new StringBuilder                for  var i   0  i  lt  names  i                    builder Append this i   Append                    return builder ToString                         static void Main                 var persons   new PersonList            for  int i   0  i  lt  100000  i                          persons Add new Person  P    i ToString    RandomString 5  true                         var unsortedPersons   new PersonList persons            const int COUNT   30          Stopwatch watch   new Stopwatch            for  int i   0  i  lt  COUNT  i                          watch Start                Sort persons               watch Stop                persons Clear                persons AddRange unsortedPersons                     Console WriteLine  Sort   0 ms   watch ElapsedMilliseconds            watch   new Stopwatch            for  int i   0  i  lt  COUNT  i                          watch Start                OrderBy persons               watch Stop                persons Clear                persons AddRange unsortedPersons                     Console WriteLine  OrderBy   0 ms   watch ElapsedMilliseconds            watch   new Stopwatch            for  int i   0  i  lt  COUNT  i                          watch Start                OrderByWithToList persons               watch Stop                persons Clear                persons AddRange unsortedPersons                     Console WriteLine  OrderByWithToList   0 ms   watch ElapsedMilliseconds              static void Sort List lt Person gt  list                list Sort  p1  p2    gt  string Compare p1 Name  p2 Name  true               static void OrderBy List lt Person gt  list                var result   list OrderBy n   gt  n Name  new NameComparer    ToArray               static void OrderByWithToList List lt Person gt  list                var result   list OrderBy n   gt  n Name  new NameComparer    ToList

User · Answer

I think it s important to note another difference between Sort and OrderBy      Suppose there exists a Person CalculateSalary   method  which takes a lot of time  possibly more than even the operation of sorting a large list   Compare     Option 1 persons Sort  p1  p2    gt  Compare p1 CalculateSalary    p2 CalculateSalary         Option 2 var query   persons OrderBy p   gt  p CalculateSalary        Option 2 may have superior performance  because it only calls the CalculateSalary method n times  whereas the Sort option might call CalculateSalary up to 2n log n  times  depending on the sort algorithm s success

User · Answer

No  they aren t the same algorithm  For starters  the LINQ OrderBy is documented as stable  i e  if two items have the same Name  they ll appear in their original order    It also depends on whether you buffer the query vs iterate it several times  LINQ-to-Objects  unless you buffer the result  will re-order per foreach    For the OrderBy query  I would also be tempted to use   OrderBy n   gt  n Name  StringComparer  yourchoice IgnoreCase      for  yourchoice  one of CurrentCulture  Ordinal or InvariantCulture    List lt T gt  Sort     This method uses Array Sort  which   uses the QuickSort algorithm  This   implementation performs an unstable   sort  that is  if two elements are   equal  their order might not be   preserved  In contrast  a stable sort   preserves the order of elements that   are equal    Enumerable OrderBy     This method performs a stable sort  that is  if the keys of two elements are equal  the order of the elements is preserved  In contrast  an unstable sort does not preserve the order of elements that have the same key    sort  that is  if two elements are   equal  their order might not be   preserved  In contrast  a stable sort   preserves the order of elements that   are equal

User · Answer

you should calculate the complexity of algorithms used by the methods OrderBy and Sort   QuickSort has a complexity of n  log n  as i remember  where n is the length of the array   i ve searched for orderby s too  but i could not find any information even in msdn library  if you have not any same values and sorting related to only one property  i prefer to use Sort   method  if not than use OrderBy

User · Answer

I just want to add that orderby is way more useful   Why  Because I can do this   Dim thisAccountBalances   account DictOfBalances Values ToList thisAccountBalances ForEach Sub x  x computeBalanceOtherFactors    thisAccountBalances thisAccountBalances OrderBy Function x  x TotalBalance  tolist listOfBalances AddRange thisAccountBalances    Why complicated comparer  Just sort based on a field  Here I am sorting based on TotalBalance   Very easy   I can t do that with sort  I wonder why  Do fine with orderBy   As for speed it s always O n

[c#] C# Sort and OrderBy comparison

Examples related to c#

Examples related to .net

Examples related to performance

Examples related to sorting

Examples related to sql-order-by