F# Parallel Array Sorting

  • Article

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

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:

https://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 Array =
    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:

parallelsortsummary

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)):

parallelsort

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.