Patent · US Active

Parallel quicksort

US10108670B2 · kind B2 · utility

1Cited by

3References

20Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Daniel Brand · Cologne, DE
Minsik Cho · Austin, US
Ruchir Puri · Peekskill, US

Key dates

Filing date	Aug 19, 2015
Grant date	Oct 23, 2018
Priority date	—
Expiry date	Nov 27, 2036

Classification

Technology area (CPC G)Physics
CPC primaryG06F16/90339
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

Methods and systems for sorting a dataset include partitioning the dataset into 2npartitions, 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.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.