Parallel bucket sorting on graphics processing units based on convex optimization

We found an interesting relation between convex optimization and sorting problem. We present a parallel algorithm to compute multiple order statistics of the data by minimizing a number of related convex functions. The computed order statistics serve as splitters that group the data into buckets suitable for parallel bitonic sorting. This led us to a parallel bucket sort algorithm, which we implemented for many-core architecture of graphics processing units (GPUs). The proposed sorting method is competitive to the state-of-the-art GPU sorting algorithms and is superior to most of them for long sorting keys.

North or south? Phylogenetic and biogeographic origins of a globally distributed avian clade

Establishing phylogenetic relationships within a clade can help to infer ancestral origins and indicate how widespread species reached their current biogeographic distributions. The small plovers, genus Charadrius, are cosmopolitan shorebirds, distributed across all continents except Antarctica. Here we present a global, species-level molecular phylogeny of this group based on four nuclear (. ADH5, FIB7, MYO2 and RAG1) and two mitochondrial (. COI and ND3) genes, and use the phylogeny to examine the biogeographic origin of the genus. A Bayesian multispecies coalescent approach identified two major clades (. CRD I and CRD II) within the genus. Clade CRD I contains three species (. Thinornis novaeseelandiae, Thinornis rubricollis and Eudromias morinellus), and CRD II one species (. Anarhynchus frontalis), that were previously placed outside the Charadrius genus. In contrast to earlier work, ancestral area analyses using parsimony and Bayesian methods supported an origin of the Charadrius plovers in the Northern hemisphere. We propose that major radiations in this group were associated with shifts in the range of these ancestral plover species, leading to colonisation of the Southern hemisphere.