Faster Sorting in C#

C# has several built-in algorithms for sorting arrays, lists and other containers. Array.Sort and List.Sort have many variations for sorting full or partial containers, using an algorithm that runs on a single CPU core. The Linq library can also sort containers, using a single CPU core or multiple cores in parallel. These are powerful, flexible, high performance capabilities. If you need to sort even faster in C# (.NET) using the CPU, this blog describes two libraries that provide alternate high performance sorting algorithms.

HPCsharp

The first library is open source NuGet package, hosted in GitHub (HPCsharp). Currently, it has Insertion Sort, Merge Sort, and Radix Sort. It also has Merge of two presorted containers. Also, Min, Max and Equal of containers, which can run on multiple cores in parallel. Sorting and Merging are not parallel algorithms in this NuGet package.

Radix Sort is a high performance implementation ported

HPCsharper

 

C# Built-in Sorting Algorithms Details

C# Array.Sort and List.Sort uses a hybrid sorting algoritm called introspective sort, which is a mixture of Insertion Sort, Heap Sort and Quicksort. “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. On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation” (msdn).

I’ll describe a library of sorting algorithms that has been developed over the last few years, which can sort faster while using a single CPU core, or multiple cores.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s