Exploiting few inversions when sorting: Sequential and parallel algorithms

DOI10.1016/0304-3975(95)00256-1zbMath0877.68034OpenAlexW2020033095MaRDI 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

Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items (2)

Adaptive sorting: an information theoretic perspective ⋮ Counting inversions adaptively

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exploiting few inversions when sorting: Sequential and parallel algorithms