Sorting Algorithms and Networks in RAM Model
Explore the world of sorting algorithms in the RAM model, including comparison-based sorting, sorting networks, and time per element analysis. Learn about efficient sorting techniques and ongoing research in the field.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Sorting Integers in the RAM Model Gerth St lting Brodal Joint work with Djamal Belazzougui and Jesper Sindal Nielsen (to be presented at the 14th Scandinavian Workshop on Algorithm Theory) MADALGO Review Meeting, April 28, 2014
Sorting (Integers) n integers 1 2 3 4 5 6 7 8 9 10 58 00111010 00001101 10001010 00110111 10001101 10001001 00001010 00110101 00001010 00110110 w bits 13 138 55 141 137 11 53 10 54 Input 00001010 00001010 00001101 00110101 00110110 00110111 00111010 10001001 10001010 10001101 10 11 13 53 54 55 58 137 138 141 Output 0 1 0 1 0 0 - - 0 - 0 1 0 1 Trie Patricia trie (branching charcters only) 0 1 0 - - - 1 0 1 1 - 0 1 - 0 0 1 - - 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 - - 0 1 - 0 1 - 0 1 1 1 0 1 0 1 0 1 0 1 - - 0 - - - - - permutation 9 7 2 8 10 4 1 6 3 5 9 7 2 8 10 4 1 6 3 5
Comparison Based Sorting Merge sort: von Neumann 1945 58 13 58 next scanning 13 13 55 58 138 13 55 58 138 138 next 55 138 scanning 55 11 13 53 55 58 137 138 141 11 13 53 55 58 137 138 141 141 137 141 next scanning 137 11 53 137 141 11 53 137 141 11 11 53 53 10 11 13 53 54 55 58 137 138 141 10 10 54 log2n comparions n 54 Ford et al. 1959: Lower bound nlog2n n ln2 comparions
Sorting Networks Input Output 138 13 13 138 13 13 138 58 55 13 55 58 55 55 58 58 58 55 58 138 55 138 Original motivated by hardware implementations Renewed interest since data-oblivious applications in privacy preserving computations allows for parallel computations on bit-level and GPU O(n log2n) size : Batcher 1968 O(n log n) size : Ajtai, Koml s, Szemer di 1983; Paterson 1990; Goodrich 2014
Time per element Results 2 O loglogn 1 3 NEW O(1) w log2n loglog n log2+ n log n O(n+2w) Bucket sort 1 w O n Radix sort; Hollerith 1887 logn van Emde Boas 1975 Willard 1983 superlinear space expected O nlogw w O n log Kirkpatrick and Reicsh 1983 logn comparison based optimal Merge sort: von Neumann 1945 O nlogn O n log(w/log n) O n loglogn Thorup and Han 2002 expected 2 expected, w log2+ n Andersson et al. 1998 O(n) 3 expected, w log2n loglogn NEW O(n)
Open Question Time per element O loglogn NEW O(1) w log2n loglog n log2+ n log n Sorting in linear time for all w?
