groovyx.gpars.extra166y
[Java] Class PAS.FJOSorter

java.lang.Object
  jsr166y.RecursiveAction
      groovyx.gpars.extra166y.PAS.FJOSorter

static final class PAS.FJOSorter
extends RecursiveAction

Sorter classes based mainly on CilkSort Cilk: Basic algorithm: if array size is small, just use a sequential quicksort Otherwise: 1. Break array in half. 2. For each half, a. break the half in half (i.e., quarters), b. sort the quarters c. merge them together 3. merge together the two halves. One reason for splitting in quarters is that this guarantees that the final sort is in the main array, not the workspace array. (workspace and main swap roles on each subsort step.) Leaf-level sorts use a Sequential quicksort, that in turn uses insertion sort if under threshold. Otherwise it uses median of three to pick pivot, and loops rather than recurses along left path. It is sad but true that sort and merge performance are sensitive enough to inner comparison overhead to warrant creating 6 versions (not just 3) -- one each for natural comparisons vs supplied comparators.

a

final java.lang.Object[] a

cmp

final java.util.Comparator cmp

gran

final int gran

n

final int n

origin

final int origin

w

final java.lang.Object[] w

PAS.FJOSorter

PAS.FJOSorter(java.util.Comparator cmp, java.lang.Object[] a, java.lang.Object[] w, int origin, int n, int gran)

compute

public void compute()

Copyright © 2008–2012 Václav Pech. All Rights Reserved.