Exploiting few inversions when sorting: Sequential and parallel algorithms

DOI10.1016/0304-3975(95)00256-1zbMath0877.68034MaRDI QIDQ1365941

Christos Levcopoulos, Ola Petersson

Publication date: 10 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00256-1

Mathematics Subject Classification ID

68P10: Searching and sorting

68W10: Parallel algorithms in computer science

68W15: Distributed algorithms

Related Items

Counting inversions adaptively, Adaptive sorting: an information theoretic perspective

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• A note on adaptive parallel sorting
• Sorting roughly sorted sequences in parallel
• A guided tour of Chernoff bounds
• Sorting in \(c \log n\) parallel steps
• Smoothsort, an alternative for sorting in situ
• An optimal parallel adaptive sorting algorithm
• Splitsort -- an adaptive sorting algorithm
• Axioms and hulls
• Smoothsort's behavior on presorted sequences
• Measures of Presortedness and Optimal Sorting Algorithms
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Parallel Merge Sort
• Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
• Expected time bounds for selection
• Adaptive Heapsort
• A framework for adaptive sorting