In previous posts I have presented code to perform Parallel Sorting of arrays using 2 different methods:

- Merge sort using Barrier: http://blogs.msdn.com/b/carlnol/archive/2011/07/17/f-array-parallel-sort-functions-demonstrating-a-merge-sort-using-barrier.aspx
- Quicksort: http://blogs.msdn.com/b/carlnol/archive/2011/07/17/f-an-array-parallel-quicksort-implementation.aspx

As the code is spread out over these post I thought it would be useful to wrap up the code into a single solution for downloading:

http://code.msdn.microsoft.com/FSharp-Parallel-Array-Sort-0833cf30

Although the two implementations can be called separately a single set of sort operations within the Array.Parallel module has been exposed:

module Parallel =

let private smallThreshold = 48 * 1024

let private largeThreshold = 2048 * 1024

let sort (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.Sort(array)

| length when length > smallThreshold -> ParallelQuickSort.Sort(array)

| _ -> Array.sort array

let sortBy (projection: 'T -> 'Key) (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.SortBy(array, projection)

| length when length > smallThreshold -> ParallelQuickSort.SortBy(array, projection)

| _ -> Array.sortBy projection array

let sortWith (comparer: 'T -> 'T -> int) (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.SortWith(array, comparer)

| length when length > smallThreshold -> ParallelQuickSort.SortWith(array, comparer)

| _ -> Array.sortWith comparer array

let sortInPlace (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.SortInPlace(array)

| length when length > smallThreshold -> ParallelQuickSort.SortInPlace(array)

| _ -> Array.sortInPlace array

let sortInPlaceBy (projection: 'T -> 'Key) (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.SortInPlaceBy(array, projection)

| length when length > smallThreshold -> ParallelQuickSort.SortInPlaceBy(array, projection)

| _ -> Array.sortInPlaceBy projection array

let sortInPlaceWith (comparer: 'T -> 'T -> int) (array: 'T []) =

match array.Length with

| length when length > largeThreshold -> ParallelMergeSort.SortInPlaceWith(array, comparer)

| length when length > smallThreshold -> ParallelQuickSort.SortInPlaceWith(array, comparer)

| _ -> Array.sortInPlaceWith comparer array

This heuristic based wrapper works on the assumption that the Quicksort is faster for under 2 million array entries; after which the Merger sort is faster. Also when there are less than 50 thousand entries in the Array then the base sequential sort is faster. Here is a summary for the sortInPlace operation:

As demonstrated, the parallel extensions support not only the sort and sortInPlace operations but the full set of possible operations; including sortBy, sortWith, sortByInPlace, and sortWithInPlace.

So how do the different sorts compare? Using my quad-core laptop with an array of 5 million floats the numbers are (the projection is defined as (sqrt << abs)):

One metric worth mentioning is that if one creates a comparer from the projection and then performs a sortInPlaceWith then the Quicksort takes about 3 seconds. This is compared with the sortInPlaceBy of about 1 second.

So if you have the need to perform parallel sort operation hopefully this will get you off the ground.