Patent · US Active

Parallel quicksort

US10671611B2 · 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 21, 2018
Grant date	Jun 2, 2020
Priority date	—
Expiry date	Aug 21, 2038

Classification

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

Abstract

A first quicksort is performed in parallel across pairs of partitions of a dataset assigned to respective ones of available processors, including swapping elements of a first partition of a given one of the pairs that are larger than a pivot with elements of a second partition of the given pair that are smaller than the pivot. A second quicksort is performed in parallel across those partitions having elements left unsorted by the first quicksort, and first misplaced elements from a first side of the dataset corresponding to the first partition are swapped with second misplaced elements from a second side of the dataset corresponding to the second partition to produce a first dataset having elements equal to or lower than the pivot and a second dataset having elements equal to or higher than the pivot.

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