PUMA publications for /user/sebastianrungehttps://puma.uni-kassel.de/user/sebastianrungePUMA RSS feed for /user/sebastianrunge2024-03-19T05:07:57+01:00On the best case of heapsorthttps://puma.uni-kassel.de/bibtex/2a740fbeb91288ba7d27b21f59a3ab7e6/sebastianrungesebastianrunge2013-07-17T15:29:41+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Bela Bollobas" itemprop="url" href="/author/Bela%20Bollobas"><span itemprop="name">B. Bollobas</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Trevor I. Fenner" itemprop="url" href="/author/Trevor%20I.%20Fenner"><span itemprop="name">T. Fenner</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Alan M. Frieze" itemprop="url" href="/author/Alan%20M.%20Frieze"><span itemprop="name">A. Frieze</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Journal of Algorithms</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">20 </span></span>(<span itemprop="issueNumber">2</span>):
<span itemprop="pagination">205-217</span></em> </span>(<em><span>März 1996<meta content="März 1996" itemprop="datePublished"/></span></em>)Wed Jul 17 15:29:41 CEST 2013Journal of Algorithmsmar2205-217On the best case of heapsort201996algorithm heapsort kdesems2013 sorting BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)https://puma.uni-kassel.de/bibtex/299f1ffe7091a547a5b1b4dc6f12a6a0c/sebastianrungesebastianrunge2013-06-17T20:12:30+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Ingo Wegener" itemprop="url" href="/author/Ingo%20Wegener"><span itemprop="name">I. Wegener</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Theoretical Computer Science</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">118 </span></span>(<span itemprop="issueNumber">1</span>):
<span itemprop="pagination">81-98</span></em> </span>(<em><span>September 1993<meta content="September 1993" itemprop="datePublished"/></span></em>)Mon Jun 17 20:12:30 CEST 2013Theoretical Computer Sciencesep181-98BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)1181993algorithm heapsort kdesems2013 sorting A variant of heapsort with almost optimal number of comparisonshttps://puma.uni-kassel.de/bibtex/24981e17b5c56a44cada07899baf9a791/sebastianrungesebastianrunge2013-06-17T20:08:24+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Svante Carlsson" itemprop="url" href="/author/Svante%20Carlsson"><span itemprop="name">S. Carlsson</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Information Processing Letters</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">24 </span></span>(<span itemprop="issueNumber">4</span>):
<span itemprop="pagination">247-250</span></em> </span>(<em><span>1987<meta content="1987" itemprop="datePublished"/></span></em>)Mon Jun 17 20:08:24 CEST 2013Information Processing Letters4247-250A variant of heapsort with almost optimal number of comparisons241987algorithm heapsort kdesems2013 sorting The analysis of heapsorthttps://puma.uni-kassel.de/bibtex/22bd2387d2b6ef2317fdbfff15b27b952/sebastianrungesebastianrunge2013-06-17T20:04:17+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Russel Schaffer" itemprop="url" href="/author/Russel%20Schaffer"><span itemprop="name">R. Schaffer</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Robert Sedgewick" itemprop="url" href="/author/Robert%20Sedgewick"><span itemprop="name">R. Sedgewick</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Journal of Algorithms</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">15 </span></span>(<span itemprop="issueNumber">1</span>):
<span itemprop="pagination">76-100</span></em> </span>(<em><span>Juli 1993<meta content="Juli 1993" itemprop="datePublished"/></span></em>)Mon Jun 17 20:04:17 CEST 2013Journal of Algorithmsjul176-100The analysis of heapsort151993algorithm heapsort kdesems2013 sorting AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processorshttps://puma.uni-kassel.de/bibtex/2d9566b0f4cca696940571e7fe068f736/sebastianrungesebastianrunge2013-06-17T19:55:55+02:00aa-sort algorithm kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Hiroshi Inoue" itemprop="url" href="/author/Hiroshi%20Inoue"><span itemprop="name">H. Inoue</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Takao Moriyama" itemprop="url" href="/author/Takao%20Moriyama"><span itemprop="name">T. Moriyama</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Hideaki Komatsu" itemprop="url" href="/author/Hideaki%20Komatsu"><span itemprop="name">H. Komatsu</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Toshio Nakatani" itemprop="url" href="/author/Toshio%20Nakatani"><span itemprop="name">T. Nakatani</span></a></span>. </span><span itemtype="http://schema.org/Book" itemscope="itemscope" itemprop="isPartOf"><em><span itemprop="name">PACT '07 Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques</span>, </em></span><em>Seite <span itemprop="pagination">189-198</span>. </em><em><span itemprop="publisher">IEEE Computer Society Washington</span>, </em>(<em><span>2007<meta content="2007" itemprop="datePublished"/></span></em>)Mon Jun 17 19:55:55 CEST 2013PACT '07 Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques189-198AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors2007aa-sort algorithm kdesems2013 sorting Insertion Sort is O(n log n)https://puma.uni-kassel.de/bibtex/2409455f54c69e7f21a6cce0eb2790e5a/sebastianrungesebastianrunge2013-06-17T11:45:19+02:00algorithm kdesems2013 librarysort sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Michael A. Bender" itemprop="url" href="/author/Michael%20A.%20Bender"><span itemprop="name">M. Bender</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Martin Farach-Colton" itemprop="url" href="/author/Martin%20Farach-Colton"><span itemprop="name">M. Farach-Colton</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Miguel A. Mosteiro" itemprop="url" href="/author/Miguel%20A.%20Mosteiro"><span itemprop="name">M. Mosteiro</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Theory of Computing Systems</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">39 </span></span>(<span itemprop="issueNumber">3</span>):
<span itemprop="pagination">391-397</span></em> </span>(<em><span>Juni 2006<meta content="Juni 2006" itemprop="datePublished"/></span></em>)Mon Jun 17 11:45:19 CEST 2013Theory of Computing Systemsjun3391-397Insertion Sort is O(n log n)392006algorithm kdesems2013 librarysort sorting Bead-Sort: A Natural Sorting Algorithmhttps://puma.uni-kassel.de/bibtex/225fb08a50046a0e9f307bc675c3075ba/sebastianrungesebastianrunge2013-06-17T11:41:16+02:00algorithm beadsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Joshua J. Arulanandham" itemprop="url" href="/author/Joshua%20J.%20Arulanandham"><span itemprop="name">J. Arulanandham</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Cristian S. Calude" itemprop="url" href="/author/Cristian%20S.%20Calude"><span itemprop="name">C. Calude</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Michael J. Dinneen" itemprop="url" href="/author/Michael%20J.%20Dinneen"><span itemprop="name">M. Dinneen</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>The Bulletin of the European Association for Theoretical Computer Science</em></span></span> </span>(<em><span>2002<meta content="2002" itemprop="datePublished"/></span></em>)Mon Jun 17 11:41:16 CEST 2013The Bulletin of the European Association for Theoretical Computer Science153-162Bead-Sort: A Natural Sorting Algorithm762002algorithm beadsort kdesems2013 sorting The Spreadsort High-performance General-case Sorting Algorithmhttps://puma.uni-kassel.de/bibtex/2ec0c471da9ba95a623cc386909adaee3/sebastianrungesebastianrunge2013-06-17T11:30:42+02:00algorithm kdesems2013 sorting spreadsort <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Steven J. Ross" itemprop="url" href="/author/Steven%20J.%20Ross"><span itemprop="name">S. Ross</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Parallel and Distributed Processing Techniques and Applications</em></span></span> </span>(<em><span>2002<meta content="2002" itemprop="datePublished"/></span></em>)Mon Jun 17 11:30:42 CEST 2013Parallel and Distributed Processing Techniques and Applications1100-1106The Spreadsort High-performance General-case Sorting Algorithm32002algorithm kdesems2013 sorting spreadsort Smoothsort, an alternative to sorting in situhttps://puma.uni-kassel.de/bibtex/27d7b6025d00e037c6c9fcbf1bf356a20/sebastianrungesebastianrunge2013-06-17T11:23:42+02:00algorithm kdesems2013 smoothsort sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Edsger W. Dijkstra" itemprop="url" href="/author/Edsger%20W.%20Dijkstra"><span itemprop="name">E. Dijkstra</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"> </span>(<em><span>1981<meta content="1981" itemprop="datePublished"/></span></em>)Mon Jun 17 11:23:42 CEST 2013Smoothsort, an alternative to sorting in situ1981algorithm kdesems2013 smoothsort sorting Algorithm 245: Treesort 3https://puma.uni-kassel.de/bibtex/2328f6c23a972d5bbe4bcb754011d6d16/sebastianrungesebastianrunge2013-06-17T11:18:50+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Robert W. Floyd" itemprop="url" href="/author/Robert%20W.%20Floyd"><span itemprop="name">R. Floyd</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Communications of the ACM</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">7 </span></span>(<span itemprop="issueNumber">12</span>):
<span itemprop="pagination">701</span></em> </span>(<em><span>Dezember 1964<meta content="Dezember 1964" itemprop="datePublished"/></span></em>)Mon Jun 17 11:18:50 CEST 2013Communications of the ACMdec12701Algorithm 245: Treesort 371964algorithm heapsort kdesems2013 sorting Algorithm 232: Heapsorthttps://puma.uni-kassel.de/bibtex/2f485e4ea9a877871b59ab503151a7f10/sebastianrungesebastianrunge2013-06-17T11:15:50+02:00algorithm heapsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="J. W. J. Williams" itemprop="url" href="/author/J.%20W.%20J.%20Williams"><span itemprop="name">J. Williams</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Communications of the ACM</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">7 </span></span>(<span itemprop="issueNumber">6</span>):
<span itemprop="pagination">347-348</span></em> </span>(<em><span>Juni 1964<meta content="Juni 1964" itemprop="datePublished"/></span></em>)Mon Jun 17 11:15:50 CEST 2013Communications of the ACMjun6347-348Algorithm 232: Heapsort71964algorithm heapsort kdesems2013 sorting Introspective sorting and selection algorithmshttps://puma.uni-kassel.de/bibtex/23279300fb7f4de5e396a18ccbc641ab7/sebastianrungesebastianrunge2013-06-17T11:12:55+02:00algorithms introsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="David R. Musser" itemprop="url" href="/author/David%20R.%20Musser"><span itemprop="name">D. Musser</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Software — Practice and Experience</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">27 </span></span>(<span itemprop="issueNumber">8</span>):
<span itemprop="pagination">983 - 993</span></em> </span>(<em><span>August 1997<meta content="August 1997" itemprop="datePublished"/></span></em>)Mon Jun 17 11:12:55 CEST 2013Software — Practice and Experienceaug8983 - 993 Introspective sorting and selection algorithms271997algorithms introsort kdesems2013 sorting Implementing quicksort programshttps://puma.uni-kassel.de/bibtex/2a7a341c1a2f1f3af42a605010a204cfa/sebastianrungesebastianrunge2013-06-17T11:07:06+02:00algorithm parallel quicksort sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Robert Sedgewick" itemprop="url" href="/author/Robert%20Sedgewick"><span itemprop="name">R. Sedgewick</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Communications of the ACM</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">21 </span></span>(<span itemprop="issueNumber">10</span>):
<span itemprop="pagination">847-857</span></em> </span>(<em><span>Oktober 1978<meta content="Oktober 1978" itemprop="datePublished"/></span></em>)Mon Jun 17 11:07:06 CEST 2013Communications of the ACMoct10847-857Implementing quicksort programs211978algorithm parallel quicksort sorting This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements to Quicksort is given, along with a discussion of how to implement it in assembly language. Analytic results describing the performance of the programs are summarized. A variety of special situations are considered from a practical standpoint to illustrate Quicksort's wide applicability as an internal sorting method which requires negligible extra storage.Quicksorthttps://puma.uni-kassel.de/bibtex/2fa584e8539f5c8d6dbf7bd8cab4578d4/sebastianrungesebastianrunge2013-06-17T11:04:01+02:00algorithm kdesems2013 quicksort sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="C. A. R. Hoare" itemprop="url" href="/author/C.%20A.%20R.%20Hoare"><span itemprop="name">C. Hoare</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>The Computer Journal</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">5 </span></span>(<span itemprop="issueNumber">1</span>):
<span itemprop="pagination">10-16</span></em> </span>(<em><span>1962<meta content="1962" itemprop="datePublished"/></span></em>)Mon Jun 17 11:04:01 CEST 2013The Computer Journal110-16Quicksort51962algorithm kdesems2013 quicksort sorting A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper. A Fast Easy Sorthttps://puma.uni-kassel.de/bibtex/29f4c8662cbc2f9d867927fa28d3ca93c/sebastianrungesebastianrunge2013-06-17T10:59:53+02:00algorithm combsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Stephen Lacey" itemprop="url" href="/author/Stephen%20Lacey"><span itemprop="name">S. Lacey</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Richard Box" itemprop="url" href="/author/Richard%20Box"><span itemprop="name">R. Box</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Byte Magazine</em></span></span> </span>(<em><span>April 1991<meta content="April 1991" itemprop="datePublished"/></span></em>)Mon Jun 17 10:59:53 CEST 2013Byte MagazineaprA Fast Easy Sort1991algorithm combsort kdesems2013 sorting An efficient variation of bubble sorthttps://puma.uni-kassel.de/bibtex/27e6ae30aca4066bc7da59f71ab013f66/sebastianrungesebastianrunge2013-06-17T10:53:10+02:00algorithm combsort kdesems2013 sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Wlodzimierz Dobosiewicz" itemprop="url" href="/author/Wlodzimierz%20Dobosiewicz"><span itemprop="name">W. Dobosiewicz</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Information Processing Letters</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">11 </span></span>(<span itemprop="issueNumber">1</span>):
<span itemprop="pagination">5-6</span></em> </span>(<em><span>August 1980<meta content="August 1980" itemprop="datePublished"/></span></em>)Mon Jun 17 10:53:10 CEST 2013Information Processing Lettersaug15-6An efficient variation of bubble sort111980algorithm combsort kdesems2013 sorting Information sorting in the application of electronic digital computers to business operationshttps://puma.uni-kassel.de/bibtex/2f9f2007fa7bd0ca52c96dfc4ab7336e7/sebastianrungesebastianrunge2013-06-15T18:11:07+02:00algorithm countingsort kdesems2013 sort sorting <meta content="thesis" itemprop="educationalUse"/><span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Harold H. Seward" itemprop="url" href="/author/Harold%20H.%20Seward"><span itemprop="name">H. Seward</span></a></span>. </span><em>Massachusetts Institute of Technology, </em><em><span itemprop="educationalUse">master's thesis</span>, </em>(<em><span>1954<meta content="1954" itemprop="datePublished"/></span></em>)Sat Jun 15 18:11:07 CEST 2013Information sorting in the application of electronic digital computers to business operationsmaster's thesis1954algorithm countingsort kdesems2013 sort sorting Fast Parallel GPU-Sorting Using A Hybrid Algorithmhttps://puma.uni-kassel.de/bibtex/23599de37f86ce715874fddd09d82447b/sebastianrungesebastianrunge2013-06-15T13:28:28+02:00cuda kdesems2013 parallel sorting <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Erik Sintorn" itemprop="url" href="/author/Erik%20Sintorn"><span itemprop="name">E. Sintorn</span></a></span>, und <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Ulf Assarsson" itemprop="url" href="/author/Ulf%20Assarsson"><span itemprop="name">U. Assarsson</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>Journal of Parallel and Distributed Computing</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">68 </span></span>(<span itemprop="issueNumber">10</span>):
<span itemprop="pagination">1381-1388</span></em> </span>(<em><span>Oktober 2008<meta content="Oktober 2008" itemprop="datePublished"/></span></em>)Sat Jun 15 13:28:28 CEST 2013Journal of Parallel and Distributed Computingoct101381-1388Fast Parallel GPU-Sorting Using A Hybrid Algorithm682008cuda kdesems2013 parallel sorting This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity nlognnlogn, and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of n(logn)2n(logn)2, which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup.