0

I know that Array.Sort() in VB.NET uses the quicksort algorithm. But my question is, does it take advantage of multithreading?

I'm sorting a list of hundreds of thousands of records, and need to ensure the fastest sort times.

Thanks.

Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794
user842818
  • 305
  • 1
  • 5
  • 14
  • Looking at the code in mscorlib, is doesn't appear to. Have you tried just running it? Does it meet your current performance goals? – dlev Jul 14 '11 at 18:22
  • This is in production code, and it takes about 4-5 seconds to sort a list of 100k rows. It's ultimately faster for me to do a requery to the database and apply the sorting in the SQL query. I don't want to do this do, so I'm not putting an extra load on our database server just to sort the results. – user842818 Jul 14 '11 at 18:25
  • What type of data are you sorting? If it's based on integer keys, then you might have some success with using a radix sort. You also might give the *appearance* of improved performance with an intelligent caching layer. Without knowing more specifics, it's hard to give much more advice. – dlev Jul 14 '11 at 18:28
  • I'm sorting my own object, which I call "Document". I contains around 20 or so properties, and is displayed in a grid. When a user clicks on a column, it basically calls the .Sort() method of a collection. I do have a class that implements IComparer to do the comparison, and there's nothing that can be done to improve its performance. – user842818 Jul 14 '11 at 18:30
  • In that case, I can't think of a lot that can be done. Sorting 100K+ records is going to be a time-consuming operation, especially with non-trivial comparands. – dlev Jul 14 '11 at 18:32
  • I would question the wisdom of putting 100K rows in a grid on the UI – Chris Dunaway Jul 15 '11 at 14:03

1 Answers1

1

I'm not sure how multi-threading would make your sorting faster.
Array.Sort does sorting in a single thread.

If by multi-threading you actually mean taking advantage of several processors when they are available, check out this answer that uses Parallel Extensions (available in .NET 4.0 and partly available for .NET 3.5).

Community
  • 1
  • 1
Dan Abramov
  • 264,556
  • 84
  • 409
  • 511
  • Thanks, this may be what I need. I'm surprised that Microsoft that does not have an impementation of this? I've been adjusting to using Parallel.ForEach() in .NET 4.0. – user842818 Jul 14 '11 at 18:34
  • Well, I'm not sure if it's going to give you a real performance boost though. I would rather try to optimize the `IComparer` using a profiler. – Dan Abramov Jul 14 '11 at 18:37
  • Also, don't hesitate posting comparer code in another question—people might notice something you might've missed, e.g. expensive boxing operations. – Dan Abramov Jul 14 '11 at 18:38
  • I guess my thought was if we have 4 processors, divide up the list into four parts, and have the 4 processors each work on sorting those 4 parts. It may be just as expensive to combine these back together. Does anyone have any hard numbers on a proven sorting algorithm that takes advantage of multiple cores, or is there not a solution? – user842818 Jul 14 '11 at 18:47
  • @user842818, check out Divide & Conquer http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm – Chris Haas Jul 14 '11 at 21:43