Discover published sets by community

Description: A non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by individual digits using threads. Best Case Time Complexity: $O(k \times \frac{n}{p})$ Worst Case Time Complexity: $O(k \times \frac{n}{p})$ Average Case Time Complexity: $O(k \times \frac{n}{p})$ where k is the maximum key length, and p is the number of processors.

Description: A parallel version of the bubble sort where the list is divided among processors which individually perform bubble sort, followed by parallel merging. Best Case Time Complexity: $O(n/p)$ Worst Case Time Complexity: $O(n^2/p)$ Average Case Time Complexity: $O(n^2/p)$ where p is the number of processors.

Description: An adaptation of quicksort that samples the array to choose better pivots to minimize the working set on each recursion. Best Case Time Complexity: $O(\log^2(n))$ Worst Case Time Complexity: $O(n \log(n))$ Average Case Time Complexity: $O(\log^2(n))$

Description: A parallelized version of counting sort, where the count operation is performed in parallel to improve efficiency for large lists of integer keys. Best Case Time Complexity: $O(n+k)$ Worst Case Time Complexity: $O(n+k)$ Average Case Time Complexity: $O(n+k)$ where k is the range of input values and assuming p processors each working on $n/p$ elements.

Description: A parallel version of the quick sort algorithm where sections of the array are split up and sorted in parallel. Best Case Time Complexity: $O(\log(n) \times \frac{n}{p})$ Worst Case Time Complexity: $O(n^2/p)$ Average Case Time Complexity: $O(n \log(n) / p)$ where p is the number of processors.

Description: A parallel version of the classic merge sort algorithm which divides the array into subarrays to sort and merge in parallel. Best Case Time Complexity: $O(\log(n) \times \frac{n}{p})$ Worst Case Time Complexity: $O(\log(n) \times \frac{n}{p})$ Average Case Time Complexity: $O(\log(n) \times \frac{n}{p})$ where p is the number of processors.

Description: A parallel sorting algorithm that builds a self-balancing multi-dimensional array from the keys to be sorted. Best Case Time Complexity: $O(n/p)$ Worst Case Time Complexity: $O(n \log(n))$ Average Case Time Complexity: $O(n \log(n))$ where p is the number of processors.

Description: A generalization of bubble sort and insertion sort, this algorithm allows the exchange of items that are far apart by sorting pairs determined by a gap sequence. Best Case Time Complexity: Depends on the gap sequence Worst Case Time Complexity: Depends on the gap sequence Average Case Time Complexity: Varies, often approximated as $O(n (\log(n))^2)$

Description: It is a parallel version of the comparison-based heap sort which involves building a heap and then repeatedly removing the largest element from the heap. Best Case Time Complexity: $O(n \log(n) / p)$ Worst Case Time Complexity: $O(n \log(n) / p)$ Average Case Time Complexity: $O(n \log(n) / p)$ where p is the number of processors.