Integer sorting in C#

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Hi Guys

What is the fastest way of sorting a huge list of Integers in C#

I was thinking of using the Array class. Is there a better way of doing this

Regards

Jack.
 
Jack,

I would use the static Sort method on the array class. You might get
some better performance by using unsafe code and shifting the integers
yourself, but I don't know how much you would get.

Hope this helps.
 
Nicholas Paldino said:
I would use the static Sort method on the array class. You might get
some better performance by using unsafe code and shifting the
integers yourself, but I don't know how much you would get.
Click to expand...

I would actually advise against using Array.Sort - it will end upboxing
every integer and unboxing it for the comparisons. It would probably be
significantly faster to copy a quicksort algorithm from somewhere
(preferably one with some sensible pivot handling to avoid worst cases)
and use that on a straight int[].
 
Jon Skeet said:
Nicholas Paldino said:
I would use the static Sort method on the array class. You might get
some better performance by using unsafe code and shifting the
integers yourself, but I don't know how much you would get.
Click to expand...

I would actually advise against using Array.Sort - it will end upboxing
every integer and unboxing it for the comparisons. It would probably be
significantly faster to copy a quicksort algorithm from somewhere
(preferably one with some sensible pivot handling to avoid worst cases)
and use that on a straight int[].
Click to expand...

I'm sure .NET 2.0 fixes this finally :)
 
Nicholas Paldino said:
Jack,

I would use the static Sort method on the array class. You might get
some better performance by using unsafe code and shifting the integers
Click to expand...

Unsafe code does not make sorting quicker.. but since a sort on an array
does not need resizing, a custom (quick) sort algorithm will help.
 
Jon,
I would actually advise against using Array.Sort - it will end upboxing
every integer and unboxing it for the comparisons.
Click to expand...

Not on any implementation I've looked at, not for szarrays of int
anyway. Array.Sort(Array) calls
Array.Sort(Array,Array,int,int,IComparer), which in turn calls
Array.TrySZSort(), which is implemented in native code and handles
optimized quicksort for all the primitive value types.



Mattias
 
Mattias Sjögren said:
Not on any implementation I've looked at, not for szarrays of int
anyway. Array.Sort(Array) calls
Array.Sort(Array,Array,int,int,IComparer), which in turn calls
Array.TrySZSort(), which is implemented in native code and handles
optimized quicksort for all the primitive value types.
Click to expand...

Ah, excellent. I'd assumed it would have to use an actual IComparer,
which would slow things down nastily.

That's good to know.
 
Egbert Nierop (MVP for IIS) said:
Jon Skeet said:
Nicholas Paldino said:
I would use the static Sort method on the array class. You might get
some better performance by using unsafe code and shifting the
integers yourself, but I don't know how much you would get.
Click to expand...

I would actually advise against using Array.Sort - it will end upboxing
every integer and unboxing it for the comparisons. It would probably be
significantly faster to copy a quicksort algorithm from somewhere
(preferably one with some sensible pivot handling to avoid worst cases)
and use that on a straight int[].
Click to expand...

I'm sure .NET 2.0 fixes this finally :)
Click to expand...

It will, as you'll have a generic ArrayList that maps value types
differently from reference types.
Hence, an ArrayList<int> would do no boxing whatsoever.

Best Regards
- Michael S
 
Egbert,

Actually, it could. Because bounds checks are not perfomed in unsafe
code you can improve the speed of swapping the elements in the array, which
is needed for sort algorithms.
 
Back
Top