@article{sintorn2008parallel,
  abstract = {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.},
  author = {Sintorn, Erik and Assarsson, Ulf},
  interhash = {db7c140766f1848f9a6f74f693d810d8},
  intrahash = {3599de37f86ce715874fddd09d82447b},
  journal = {Journal of Parallel and Distributed Computing},
  month = oct,
  number = 10,
  pages = {1381-1388},
  title = {Fast Parallel GPU-Sorting Using A Hybrid Algorithm},
  url = {http://www.sciencedirect.com/science/article/pii/S0743731508001196},
  volume = 68,
  year = 2008
}

@mastersthesis{seward1954information,
  author = {Seward, Harold H.},
  interhash = {dc55dfc2ceec31b94a8d249da464bd67},
  intrahash = {f9f2007fa7bd0ca52c96dfc4ab7336e7},
  school = {Massachusetts Institute of Technology},
  title = {Information sorting in the application of electronic digital computers to business operations},
  type = {master's thesis},
  year = 1954
}

@article{dobosiewicz1980efficient,
  author = {Dobosiewicz, Wlodzimierz},
  interhash = {871521972819cf2a12a253a835242437},
  intrahash = {7e6ae30aca4066bc7da59f71ab013f66},
  journal = {Information Processing Letters},
  month = aug,
  number = 1,
  pages = {5-6},
  title = {An efficient variation of bubble sort},
  url = {http://www.sciencedirect.com/science/article/pii/0020019080900228},
  volume = 11,
  year = 1980
}

@article{lacey1991,
  author = {Lacey, Stephen and Box, Richard},
  interhash = {98a38e832498c064ae105d0be1fa5ec1},
  intrahash = {9f4c8662cbc2f9d867927fa28d3ca93c},
  journal = {Byte Magazine},
  month = apr,
  title = {A Fast Easy Sort},
  year = 1991
}

@article{hoare1962quicksort,
  abstract = {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. },
  author = {Hoare, C. A. R.},
  interhash = {90334d822bec08f9800dd538623e34f0},
  intrahash = {fa584e8539f5c8d6dbf7bd8cab4578d4},
  journal = {The Computer Journal},
  number = 1,
  pages = {10-16},
  title = {Quicksort},
  url = {http://comjnl.oxfordjournals.org/content/5/1/10},
  volume = 5,
  year = 1962
}

@article{musser1997introspective,
  author = {Musser, David R.},
  interhash = {e2eb9a859abb44066bb771e742225e8a},
  intrahash = {3279300fb7f4de5e396a18ccbc641ab7},
  journal = {Software — Practice and Experience},
  month = aug,
  number = 8,
  pages = {983 - 993 },
  title = {Introspective sorting and selection algorithms},
  volume = 27,
  year = 1997
}

@article{williams1964algorithm,
  author = {Williams, J. W. J.},
  interhash = {88f7b4bad2300e0db2fab61c269e1f4e},
  intrahash = {f485e4ea9a877871b59ab503151a7f10},
  journal = {Communications of the ACM},
  month = jun,
  number = 6,
  pages = {347-348},
  title = {Algorithm 232: Heapsort},
  volume = 7,
  year = 1964
}

@article{floyd1964algorithm,
  author = {Floyd, Robert W.},
  interhash = {baf7da69dff2f4d24c091a9deb2f7bdb},
  intrahash = {328f6c23a972d5bbe4bcb754011d6d16},
  journal = {Communications of the ACM},
  month = dec,
  number = 12,
  pages = 701,
  title = {Algorithm 245: Treesort 3},
  volume = 7,
  year = 1964
}

@article{dijkstra1981smoothsort,
  author = {Dijkstra, Edsger W.},
  interhash = {ccce70335c6360e94cadf86bc1cfb86a},
  intrahash = {7d7b6025d00e037c6c9fcbf1bf356a20},
  title = {Smoothsort, an alternative to sorting in situ},
  year = 1981
}

@article{ross2002spreadsort,
  author = {Ross, Steven J.},
  interhash = {8d6f28a42466de9d2ea4cc9c11884d49},
  intrahash = {ec0c471da9ba95a623cc386909adaee3},
  journal = {Parallel and Distributed Processing Techniques and Applications},
  pages = {1100-1106},
  title = {The Spreadsort High-performance General-case Sorting Algorithm},
  volume = 3,
  year = 2002
}

@article{arulanandham2002beadsort,
  author = {Arulanandham, Joshua J. and Calude, Cristian S. and Dinneen, Michael J.},
  interhash = {716ba2d9290a62668130a49d0f3133e3},
  intrahash = {25fb08a50046a0e9f307bc675c3075ba},
  journal = {The Bulletin of the European Association for Theoretical Computer Science},
  pages = {153-162},
  title = {Bead-Sort: A Natural Sorting Algorithm},
  volume = 76,
  year = 2002
}

@article{bender2006insertion,
  author = {Bender, Michael A. and Farach-Colton, Martin and Mosteiro, Miguel A.},
  interhash = {b27269a00ac2b9c0f78375cb8f712c1b},
  intrahash = {409455f54c69e7f21a6cce0eb2790e5a},
  journal = {Theory of Computing Systems},
  month = jun,
  number = 3,
  pages = {391-397},
  title = {Insertion Sort is O(n log n)},
  volume = 39,
  year = 2006
}

@inproceedings{inoue2007aasort,
  author = {Inoue, Hiroshi and Moriyama, Takao and Komatsu, Hideaki and Nakatani, Toshio},
  booktitle = {PACT '07 Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques},
  interhash = {bc1e876542ce12b7385d44386ee04c67},
  intrahash = {d9566b0f4cca696940571e7fe068f736},
  pages = {189-198},
  publisher = {IEEE Computer Society Washington},
  title = {AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors},
  year = 2007
}

@article{schaffer1993analysis,
  author = {Schaffer, Russel and Sedgewick, Robert},
  interhash = {40b92ad6147010e002ad4bdf6eaf0e7b},
  intrahash = {2bd2387d2b6ef2317fdbfff15b27b952},
  journal = {Journal of Algorithms},
  month = jul,
  number = 1,
  pages = {76-100},
  publisher = {Academic Press},
  title = {The analysis of heapsort},
  volume = 15,
  year = 1993
}

@article{carlsson1987variant,
  author = {Carlsson, Svante},
  interhash = {dbf90c28ff8293fee436d214e62254ba},
  intrahash = {4981e17b5c56a44cada07899baf9a791},
  journal = {Information Processing Letters},
  number = 4,
  pages = {247-250},
  publisher = {Elsevier},
  title = {A variant of heapsort with almost optimal number of comparisons},
  volume = 24,
  year = 1987
}

@article{wegener1993bottomupheapsort,
  author = {Wegener, Ingo},
  interhash = {1876a3b7aac290a08d7c855e50bcdfef},
  intrahash = {99f1ffe7091a547a5b1b4dc6f12a6a0c},
  journal = {Theoretical Computer Science},
  month = sep,
  number = 1,
  pages = {81-98},
  title = {BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)},
  volume = 118,
  year = 1993
}

@article{bollobas1996heapsort,
  author = {Bollobas, Bela and Fenner, Trevor I. and Frieze, Alan M.},
  interhash = {ee3290a0e1cdd114092029bde4f2346f},
  intrahash = {a740fbeb91288ba7d27b21f59a3ab7e6},
  journal = {Journal of Algorithms},
  month = mar,
  number = 2,
  pages = {205-217},
  title = {On the best case of heapsort},
  volume = 20,
  year = 1996
}