PARALLEL QUICKSORT

摘要

Methods and systems for sorting a dataset include partitioning the dataset into 2n partitions, where n is a number of available processors. A first quicksort is performed in parallel across pairs of partitions based on a pivot using a plurality of processors. A second quicksort is performed in parallel on unsorted elements within each partition based on the pivot, where the unsorted elements were left unsorted by the first quicksort. Misplaced elements from a left side of the dataset are swapped with misplaced elements from a right side of the dataset to produce a left dataset that has elements equal to or lower than the pivot and a right dataset that has elements equal to or higher than the pivot.

主权项

1. A method for sorting a dataset, comprising:
partitioning the dataset into 2n partitions, where n is a number of available processors; performing a first quicksort in parallel across pairs of partitions based on a pivot using a plurality of processors; performing a second quicksort in parallel on unsorted elements within each partition based on the pivot, wherein the unsorted elements were left unsorted by the first quicksort; and swapping misplaced elements from a left side of the dataset with misplaced elements from a right side of the dataset to produce a left dataset that has elements equal to or lower than the pivot and a right dataset that has elements equal to or higher than the pivot.