@preamble{ "\newcommand{\SortNoop}[1]{} "}
@string{comment = "Last change 21.8.2001"}


@book{AHU74,
   author =    {Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman},
   title =     {The Design and Analysis of Computer Algorithms},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1974
}

@Unpublished{KPRT01,
  author = 	 {Jyrki Katajainen and Tomi A. Pasanen and Laurent Rosaz and Jukka Teuhola},
  title = 	 {Analysis of top-down heapsort and its variants},
  note = 	 {In preparation},
  year =	 {to appear},
}

@book{AHU83,
   author =    {Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman},
   title =     {Data Structures and Algorithms},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1983
}

@article{ASSS86,
   author =  {M. D. Atkinson and J.-R. Sack and N. Santoro and T. Strothotte},
   title =   {Min-max heaps and generalized priority queues},
   journal = cacm,
   volume =  29,
   pages =   {996--1000},
   year =    1986
}

@InProceedings{And96,
  author = 	 {Arne Andersson},
  title = 	 {Sorting and searching revisited},
  booktitle = 	 PROC # { 5th } # SWAT,
  pages =	 {185--197},
  year =	 1996,
  volume =	 1097,
  series =	 LNCS,
  publisher =	 {Springer-Verlag},
  address =      {Berlin/\allowbreak{}Heidelberg, Germany}
}

@article{B-CK86,
   author =  {Huang Bing-Chao and Donald E. Knuth},
   title =   {A one-way, stackless {Q}uicksort algorithm},
   journal = bit,
   year =    1986,
   volume =  26,
   pages =   {127--130}
}

@article{BFF96,
   author =  {B. Bollob\'{a}s and T. I. Fenner and A. M. Frieze},
   title =   {On the best case of {H}eapsort},
   journal = jalg,
   year =    1996,
   volume =  20,
   pages =   {205--217}
}

@article{BFHUW88,
   author =  {Allan Borodin and Faith E. Fich and Friedhelm Meyer auf
		  der Heide and Eli Upfal and Avi Wigderson},
   title =   {A tradeoff between search and update time for the implicit 
              dictionary problem},
   journal = tcs,
   volume =  58,
   year =    1988,
   pages =   {57--68}
}

@article{BFPRT73,
   author =  {Manuel Blum and Robert W. Floyd and Vaughan Pratt and Ronald L. 
              Rivest and Robert E. Tarjan},
   title =   {Time bounds for selection},
   journal = jcss,
   year =    1973,
   volume =  7,
   pages =   {448--461}
}
@inproceedings{BJ85,
   author =    {Samuel W. Bent and John W. John},
   title =     {Finding the median requires $2n$ comparisons},
   booktitle = PROC # { 17th Annual } # STOC,
   year =      1985,
   publisher = {ACM},
   address =   {New York, New York},
   pages =     {213--216}
}
@article{BKS00,
   author =  {Jesper Bojesen and Jyrki Katajainen and Maz Spork},
   title =   {Performance engineering case study: heap construction},
   journal = {The ACM Journal of Experimental Algorithmics},
   year =    {to appear},
}
@InProceedings{BKS99,
  author = 	 {Jesper Bojesen and Jyrki Katajainen and Maz Spork},
  title = 	 {Performance engineering case study: heap construction},
  booktitle = 	 PROC # { 3rd Workshop on Algorithm Engineering},
  pages =	 {301--315},
  year =	 1999,
  volume =	 {1668},
  series =	 LNCS,
  publisher =	 {Springer-Verlag},
  address =      {Berlin/\allowbreak{}Heidelberg, Germany}
}

@article{BM93,
   author =  {Jon L. Bentley and M. Douglas Mc{I}lroy},
   title =   {Engineering a sort function},
   journal = software,
   year =    1993,
   volume =  23,
   pages =   {1249--1265}
}


@inproceedings{BM94,
   author =    {Andrej Brodnik and J. Ian Munro},
   title =     {Membership in constant time and minimum space},
   booktitle = PROC # { 2nd Annual } # ESA,
   volume =    855,
   series =    LNCS,
   year =      1994,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {72--81}
}

@article{BS79,
   author =  {Jon Louis Bentley and James B. Saxe},
   title =   {Algorithms on vector sets},
   journal = {SIGACT News},
   year =    1979,
   volume =  11,
   number =  2,
   pages =   {36--39}
}

@article{BS80,
   author =  {Jon Louis Bentley and James B. Saxe},
   title =   {Decomposable searching problems I.~Static-to-dynamic 
              transformation},
   journal = jalg,
   year =    1980,
   volume =  1,
   pages =   {301--358}
}

@PREAMBLE{"\newcommand{\THOMAS}{T}"}
@article{BT79,
   author =  {Mark R. Brown and Robert E. Tarjan},
   title =   {A fast merging algorithm},
   journal = jacm,
   year =    1979,
   volume =  26,
   pages =   {211--226}
}
@book{Ben86,
   author =    {Jon Bentley},
   title =     {Programming Pearls},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1986
}
@book{Ben88,
   author =    {Jon Bentley},
   title =     {More Programming Pearls: Confessions of a Coder},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1986
}
@Article{Ben92,
  author = 	 {Jon L. Bentley},
  title = 	 {Software exploratorium: history of a Heapsort},
  journal =  {UNIX Review},
  year = 	 1992,
  volume =	 10,
  number =	 8,
  pages =	 {71--77}
}
@Article{Bit82,
  author = 	 {James R. Bitner},
  title = 	 {An asymptotically optimal algorithm for the {D}utch 
                  national flag problem},
  journal = 	 sicomp,
  year = 	 1982,
  volume =	 11,
  pages =	 {243--262}
}
@article{Bur76,
   author =  {William H. Burge},
   title =   {An analysis of binary search trees formed from sequences of 
              nondistinct keys},
   journal = jacm,
   year =    1976,
   volume =  23,
   pages =   {451--454}
}
@InProceedings{CC00,
  author = 	 {Domenico Cantone and Gianluca Cincotti},
  title = 	 {Quick{H}eapsort, an Efficient Mix of Classical Sorting Algorithms},
  booktitle = {Proceedings of the 4th Italian Conference on Algorithms and Complexity},
pages = {150--162},
  year =	 2000,
  series =	 LNCS,
  volume = 1767,
  publisher =	 {Springer-Verlag},
  address =      {Berlin/\allowbreak{}Heidelberg, Germany}
}
@InProceedings{CC92,
  author =       "Svante Carlsson and Jingsen Chen",
  title =        "The Complexity of Heaps",
  booktitle =    "Proceedings of the 3rd Annual ACM-SIAM Symposium on
                 Discrete Algorithms",
  year =         "1992",
  pages =        "393--402",
  organization = "ACM-SIAM",
  publisher =    "ACM Press",
  address =      "New York, New York",
}
@inproceedings{CC95,
   author =    {Svante Carlsson and Jingsen Chen},
   title =     {Heap construction: optimal in both worst and average cases?},
   booktitle = PROC # {  6th } # ISAAC,
   volume =    1004,
   series =    LNCS,
   year =      1995,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {254--263}
}
@article{CCM96,
   author =  {Svante Carlsson and Jingsen Chen and Christer Mattsson},
   title =   {Heaps with bits},
   journal = tcs,
   year =    1996,
   volume =  164,
   pages =   {1--12}
}
@article{CCS89,
  author = 	 {Svante Carlsson and Jingsen Chen and Thomas Strothotte},
  title = 	 {A note on the construction of the data structure ``deap''},
  journal = 	 ipl,
  year = 	 1989,
  volume =	 31,
  pages =	 {315--317}
}
@inproceedings{CGPR95,
   author =    {Maxime Crochemore and Leszek G\c{a}sieniec and Wojciech 
                Plandowski and Wojciech Rytter},
   title =     {Two-dimensional pattern matching in linear time and 
		  small space},
   booktitle = PROC # { 12th Annual } # STACS,
   series =    LNCS,
   volume =    900,
   year =      1995,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {181--192}
}
@inproceedings{CKR92,
   author =    {W. Cunto and S. Kashima and M. Rey},
   title =     {A new algorithm for selecting the median, two
                  quartiles, minimum and maximum of a set of numbers},
   booktitle = {Algorithms, Software, Architecture},
   series =    PROC # { 12th IFIP World Computer Congress},
   volume =    {I},
   year =      1992,
   publisher = {North-Holland},
   address =   {Amsterdam, The Netherlands},
   pages =     {443--448}
}

@inproceedings{CKT92,
   author =    {Svante Carlsson and Jyrki Katajainen and Jukka Teuhola},
   title =     {In-place linear probing sort},
   booktitle = PROC # {  9th Annual } # STACS,
   volume =    577,
   series =    LNCS,
   year =      1992,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {581--587}
}
@book{CLR90,
   author =    {Thomas H. Cormen and Charles E. Leiserson and 
		  Ronald L. Rivest},
   title =     {Introduction to Algorithms},
   publisher = {The MIT Press},
   address =   {Cambridge, Massachusetts},
   year =      1990
}
@article{CM89,
   author =  {Walter Cunto and J. Ian Munro},
   title =   {Average case selection},
   journal = jacm,
   year =    1989,
   volume =  36,
   pages =   {270--279}
}
@inproceedings{CMP88,
   author =    {Svante Carlsson and J. Ian Munro and Patricio V. Poblete},
   title =     {An implicit binomial queue with constant insertion time},
   booktitle = PROC # { 1st } # SWAT,
   volume =    318,
   series =    LNCS,
   year =      1988,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {1--13}
}
@inproceedings{CS95,
   author =    {Svante Carlsson and Mikael Sundstr{\"o}m},
   title =     {Linear-time in-place selection in less than $3n$ comparisons},
   booktitle = PROC # { 6th } # ISAAC,
   volume =    1004,
   series =    LNCS,
   year =      1995,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {244--253},
   note =      {A longer version is available at 
                \url{http://www.sm.luth.se/~msm/publications.html}.}
}
@phdthesis{Car86a,
   author =  {Svante Carlsson},
   title =   {Heaps},
   school =  {Department of Computer Science, Lund University},
   address = {Lund, Sweden},
   year =    1986
}
@article{Car86b,
   author =  {Svante Carlsson},
   title =   {Splitmerge---{A} fast stable merging algorithm},
   journal = ipl,
   year =    1986,
   volume =  22,
   pages =   {189--192}
}
@article{Car87,
   author =  {Svante Carlsson},
   title =   {The deap---{A} double-ended heap to implement double-ended
		  priority queues},
   journal = ipl,
   year =    1987,
   volume =  26,
   pages =   {33--36}
}
@article{Car87a,
   author =  {Svante Carlsson},
   title =   {Average-case result on {H}eapsort},
   journal = bit,
   year =    1987,
   volume =  27,
   pages =   {2--17}
}
@article{Car87b,
   author =  {Svante Carlsson},
   title =   {A variant of {H}eapsort with almost optimal number of
		  comparisons},
   journal = ipl,
   year =    1987,
   volume =  24,
   pages =   {247--250}
}
@Article{Car91,
  author =       "Svante Carlsson",
  title =        "An optimal algorithm for deleting the root of a heap",
  journal =      ipl,
  volume =       "37",
  pages =        "117--120",
  year =         "1991",
}
@article{Car92,
   author =  {Svante Carlsson},
   title =   {A note on {H}EAPSORT},
   journal = cj,
   year =    1992,
   volume =  35,
   pages =   {410--411}
}
@inproceedings{Che93,
   author =    {Jingsen Chen},
   title =     {A framework for constructing heap-like structures in-place},
   booktitle = PROC # { 4th } # ISAAC,
   volume =    762,
   series =    LNCS,
   year =      1993,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {118--127}
}
@article{Che95,
   author =  {Jingsen Chen},
   title =   {An efficient construction algorithm for a class of implicit 
              double-ended priority queues},
   journal = cj,
   year =    1995,
   volume =  38,
   pages =   {818--821}
}
@article{D72,
   author =  {A. J. W. Duijvestijn},
   title =   {Correctness proof of an in-place permutation},
   journal = bit,
   volume =  12,
   pages =   {318--324},
   year =    1972
}
@article{DD81,
   author =  {Krzysztof Dudzi\'{n}ski and Andrzej Dydek},
   title =   {On stable minimum storage merging algorithm},
   journal = ipl,
   year =    1981,
   volume =  12,
   pages =   {5--8}
}
@inproceedings{DD86,
   author =    {S. Dvo\v{r}\'{a}k and B. \v{D}urian},
   title =     {Towards an efficient merging},
   booktitle = PROC # { 12th Symposium on } # MFCS,
   volume =    233,
   series =    LNCS,
   year =      1986,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {290--298}
}
@article{DD87,
   author =  {S. Dvo\u{r}\'{a}k and B. \u{D}urian},
   title =   {Stable linear time sublinear space merging},
   journal = cj,
   year =    1987,
   volume =  30,
   pages =   {372--375}
}
@article{DD88a,
   author =  {S. Dvo\u{r}\'{a}k and B. \u{D}urian},
   title =   {Unstable linear time $O(1)$ space merging},
   journal = cj,
   year =    1988,
   volume =  31,
   pages =   {279--282}
}
@article{DD88b,
   author =  {S. Dvo\u{r}\'{a}k and B. \u{D}urian},
   title =   {Merging by decomposition revisited},
   journal = cj,
   year =    1988,
   volume =  31,
   pages =   {553--556}
}
@Article{DG82,
  author = 	 {Edsger W. Dijkstra and A. J. M. van Gasteren},
  title = 	 {An introduction to three algorithms for sorting in situ},
  journal = 	 ipl,
  year = 	 1982,
  volume =	 15,
  pages =	 {129--134}
}
@Article{DHUZ01,
  author = 	 {Dorit Dor and Johan H{\aa}stad and Staffan Ulfberg and Uri Zwick},
  title = 	 {On lower bounds for selecting the median},
  journal = 	 {SIAM Journal on Discrete Mathematics},
  year = 	 2001,
  volume =	 14,
  pages =	 {299--311}
}
@Article{DZ99,
  author = 	 {Dorit Dor and Uri Zwick},
  title = 	 {Selecting the median},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1999,
  volume =	 28,
  pages =	 {1722--1758}
}
@Article{DZ01,
  author = 	 {Dorit Dor and Uri Zwick},
  title = 	 {Median selection requires $(2+\epsilon)n$ comparisons},
  journal = 	 {SIAM Journal on Discrete Mathematics},
  year = 	 2001,
  volume =	 14,
  pages =	 {312--325}
}
@article{Dew74,
   author =  {Robert B. K. Dewar},
   title =   {A stable minimum storage sorting algorithm},
   journal = ipl,
   year =    1974,
   volume =  2,
   pages =   {162--164}
}
@book{Dij76,
   author =    {Edsger W. Dijkstra},
   title =     {A Discipline of Programming},
   publisher = {Prentice-Hall},
   address =   {Englewood Cliffs, New Jersey},
   year =      1976
}
@article{Dij82,
   author =  {Edsger W. Dijkstra},
   title =   {Smoothsort, an alternative for sorting in situ},
   journal = scp,
   year =    1982,
   volume =  1,
   pages =   {223--233},
   note =    {Errata, \textit{ibidem} \textbf{2} (1982), 85}
}
@article{Dob84,
   author =  {Ernst E. Doberkat},
   title =   {An average case analysis of {F}loyd's algorithm to construct 
              heaps},
   journal = infcon,
   year =    1984,
   volume =  61,
   pages =   {114--131}
}
@inproceedings{Dur86,
   author =    {Branislav \v{D}urian},
   title =     {Quicksort without a stack},
   booktitle = PROC # { 12th Symposium on } # MFCS,
   volume =    233,
   series =    LNCS,
   year =      1986,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {283--289}
}
@article{Dut93,
   author =  {Ronald D. Dutton},
   title =   {Weak-heap sort},
   journal = bit,
   year =    1993,
   volume =  33,
   pages =   {372--381}
}
@InProceedings{ES00,
  author = 	 {Stefan Edelkamp and Ingo Wegener},
  title = 	 {Pushing the Limits in Sequential Sorting},
  booktitle = {Proceedings of the 4th International Workshop on Algorithm Engineering},
  year =	 {to appear},
  series =	 LNCS,
  publisher =	 {Springer-Verlag},
  address =      {Berlin/\allowbreak{}Heidelberg, Germany}
}
@InProceedings{EW00,
  author = 	 {Stefan Edelkamp and Ingo Wegener},
  title = 	 {On the Performance of {W}EAK-{H}EAPSORT},
  booktitle = {Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science},
  pages =	 {254--266},
  year =	 2000,
  volume =	 1770,
  series =	 LNCS,
  publisher =	 {Springer-Verlag},
  address =      {Berlin/\allowbreak{}Heidelberg, Germany}
}
@article{EW92,
   author =  {Vladimir Estivill-Castro and Derick Wood},
   title =   {A survey of adaptive sorting algorithms},
   journal = acmcs,
   volume =  24,
   year =    1992,
   pages =   {441--476}
}
@article{FMP95,
   author =  {Faith E. Fich and J. Ian Munro and Patricio V. Poblete},
   title =   {Permuting in place},
   journal = sicomp,
   year =    1995,
   volume =  24,
   pages =   {266--278}
}
@article{FR75a,
   author =  {Robert W. Floyd and Ronald L. Rivest},
   title =   {Expected time bounds for selection},
   journal = cacm,
   year =    "{\SortNoop{1974}}1975",
   volume =  18,
   pages =   {165--172}
}
@article{FR75b,
   author =  {Robert W. Floyd and Ronald L. Rivest},
   title =   {Algorithm 489: The algorithm {S}ELECT---for finding the $i$th 
              smallest of $n$ elements},
   journal = cacm,
   year =    "{\SortNoop{1975}}1975",
   volume =  18,
   pages =   173
}
@InProceedings{Fis86,
  author = 	 {{\THOMAS{}}  M. Fisher},
  title = 	 {Redefined bounds on the complexity of sorting and selection 
                  in d-dimensional space},
  booktitle = PROC # { 12th Symposium on } # MFCS,
  pages =	 {308--314},
  year =	 1986,
  volume =	 233,
  series =	 LNCS,
  publisher =	 {Springer-Verlag}
}
@inproceedings{Fle91,
   author =    {Rudolf Fleischer},
   title =     {A tight lower bound for the worst case of 
                {B}ottom-{U}p-{H}eapsort},
   booktitle = PROC # { 2nd } # ISA,
   volume =    557,
   series =    LNCS,
   year =      1991,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {251--262}
}
@article{Flo62,
   author =  {Robert W. Floyd},
   title =   {Algorithm 113: {T}REESORT},
   journal = cacm,
   year =    1962,
   volume =  5,
   pages =   434
}
@article{Flo64,
   author =  {Robert W. Floyd},
   title =   {Algorithm 245: {T}REESORT 3},
   journal = cacm,
   year =    1964,
   volume =  7,
   pages =   701
}
@article{Fre83,
   author =  {Greg N. Frederickson},
   title =   {Implicit data structures for the dictionary problem},
   journal = jacm,
   year =    1983,
   volume =  30,
   pages =   {80--94}
}
@article{Fre84a,
   author =  {Greg N. Frederickson},
   title =   {Recursively rotated orders and impicit data structures: A lower 
              bound},
   journal = tcs,
   year =    1984,
   volume =  29,
   pages =   {75--85}
}
@article{Fre84b,
   author =  {Greg N. Frederickson},
   title =   {Self-organizing heuristics for implicit data structures},
   journal = sicomp,
   year =    1984,
   volume =  13,
   pages =   {277--291}
}
@article{Fri56,
   author =  {Edward Harry Friend},
   title =   {Sorting on electronic computer systems},
   journal = jacm,
   year =    1956,
   volume =  3,
   pages =   {134--168}
}
@book{GB91,
   author =    {G. H. Gonnet and R. Baeza-Yates},
   title =     {Handbook of Algorithms and Data Structures: In Pascal and C},
   edition =   {2.},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Wokingham, England},
   year =      1991
}
@article{GJ82,
   author =  {Teofilo F. Gonzalez and Donald B. Johnson},
   title =   {Sorting numbers in linear expected time and optimal extra space},
   journal = ipl,
   year =    1982,
   volume =  15,
   pages =   {119--124}
}
@article{GKP00,
  author = 	 {Viliam Geffert and Jyrki Katajainen and Tomi Pasanen},
  title = 	 {Asymptotically efficient in-place merging},
  journal = 	 {Theoretical Computer Science},
  volume = 237,
  year = 2000,
  pages = {159--181},
}
@book{GKP89,
   author =    {Ronald L. Graham and Donald E. Knuth and Oren Patashnik},
   title =     {Concrete Mathematics: A Foundation for Computer Science},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1989
}

@article{GKP96,
   author =  {William Gasarch and Wayne Kelly and William Pugh},
   title =   {Finding the $i$th largest of $n$ for small~$i$,~$n$},
   journal = {SIGACT News},
   year =    1996,
   volume =  27,
   number =  2,
   pages =   {88--96}
}
@article{GM86,
   author =  {Gaston H. Gonnet and J. Ian Munro},
   title =   {Heaps on heaps},
   journal = sicomp,
   year =    1986,
   volume =  15,
   pages =   {964--971}
}
@article{GN91,
   author =  {Giorgio Gambosi and Enrico Nardelli},
   title =   {A pointer-free data structure for merging heaps and 
		  min-max heaps},
   journal = tcs,
   year =    1991,
   volume =  84,
   pages =   {107--126}
}
@article{GZ96,
   author =  {Xunrang Gu and Yuzhang Zhu},
   title =   {Optimal heapsort algorithm},
   journal = tcs,
   year =    1996,
   volume =  163,
   pages =   {239--243}
}
@Unpublished{Gef00,
  author = 	 {Viliam Geffert},
  title = 	 {Linear-time in-place selection in $\varepsilon\cdot n$ element moves},
  note = 	 {Unpublished typescript},
  year =	 2000
}
@article{H63,
   author =  {Thomas N. Hibbard},
   title =   {An empirical study of minimal storage sorting},
   journal = cacm,
   volume =  6,
   pages =   {206--213},
   year =    1963
}
@article{HD91,
   author =  {Ryan Hayward and Colin McDiarmid},
   title =   {Average case analysis of heap building by repeated insertion},
   journal = jalg,
   year =    1991,
   volume =  12,
   pages =   {126--153}
}
@article{HL72,
   author =  {F. K. Hwang and S. Lin},
   title =   {A simple algorithm for merging two disjoint linearly 
		  ordered sets},
   journal = sicomp,
   year =    1972,
   volume =  1,
   pages =   {31--39}
}
@article{HL88,
   author =  {Bing-Chao Huang and Michael A. Langston},
   title =   {Practical in-place merging},
   journal = cacm,
   year =    1988,
   volume =  31,
   pages =   {348--352}
}
@article{HL89,
   author =  {Bing-Chao Huang and Michael A. Langston},
   title =   {Stable dublicate-key extraction with optimal time and space 
              bounds},
   journal = acta,
   year =    1989,
   volume =  26,
   pages =   {473--484}
}
@article{HL92,
   author =  {B-C. Huang and M. A. Langston},
   title =   {Fast stable merging and sorting in constant extra space},
   journal = cj,
   year =    1992,
   volume =  35,
   pages =   {643--650}
}
@book{HS78,
   author =    {Ellis Horowitz and Sartaj Sahni},
   title =     {Fundamentals of Computer Algorithms},
   publisher = {Computer Science Press},
   address =   {Rockville, Maryland},
   year =      1978
}
@Article{Her83,
  author = 	 {Stefan Hertel},
  title = 	 {Smoothsort's behavior on presorted sequences},
  journal = 	 ipl,
  year = 	 1983,
  volume =	 16,
  pages =	 {165--170}
}
@article{Hoa61f,
   author =  {C. A. R. Hoare},
   title =   {Algorithm 65: {F}IND},
   journal = cacm,
   year =    1961,
   volume =  4,
   pages =   {321--322}
}
@article{Hoa61p,
   author =  {C. A. R. Hoare},
   title =   {Algorithm 63: {P}ARTITION},
   journal = cacm,
   year =    1961,
   volume =  4,
   pages =   321
}
@article{Hoa61q,
   author =  {C. A. R. Hoare},
   title =   {Algorithm 64: {Q}UICKSORT},
   journal = cacm,
   year =    1961,
   volume =  4,
   pages =   321
}
@article{Hoa62,
   author =  {C. A. R. Hoare},
   title =   {Quicksort},
   journal = cj,
   year =    1962,
   volume =  5,
   pages =   {10--15}
}
@article{Hor78,
   author =  {Edward C. Horvath},
   title =   {Stable sorting in asymptotically optimal time and extra space},
   journal = jacm,
   year =    1978,
   volume =  25,
   pages =   {177--199}
}
@manual{ISO98,
key = {ISO/IEC},
organization = {ISO (the International Organization for Standardization) 
                and IEC (the International Electrotechnical Commission)},
title = {International Standard ISO/IEC 14882: Programming Languages --- C\texttt{++}},
address =  {Gen\`{e}ve, Switzerland},
year = 1998,
}
@book{Ive62,
   author =    {Kenneth E. Iverson},
   title =     {A Programming Language},
   publisher = {John Wiley and Sons, Inc.},
   address =   {New York, New York},
   year =      1962
}
@book{Jaj92,
   author =    {Joseph J\'{a}J\'{a}},
   title =     {An Introduction to Parallel Algorithms},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1992
}
@Article{Joh88,
  author = 	 {John Welliaveetil John},
  title = 	 {A new lower bound for the set-partitioning problem},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1988,
  volume =	 17,
  pages =	 {640--647}
}
@article{KLP93,
   author =  {J. Katajainen and C. Levcopoulos and O. Petersson},
   title =   {Space-efficient parallel merging},
   journal = ita,
   year =    1993,
   volume =  27,
   pages =   {295--310}
}
@article{KP92,
   author =  {Jyrki Katajainen and Tomi Pasanen},
   title =   {Stable minimum space partitioning in linear time},
   journal = bit,
   year =    1992,
   volume =  32,
   pages =   {580--585}
}
@article{KP94,
   author =  {Jyrki Katajainen and Tomi Pasanen},
   title =   {Sorting multiset stably in minimum space},
   journal = acta,
   year =    1994,
   volume =  31,
   pages =   {301--313}
}
@article{KP99,
   author =  {Jyrki Katajainen and Tomi A. Pasanen},
   title =   {In-place sorting with fewer moves},
   journal =  ipl,
   volume =   70,
   pages =    {31--37},
   year =     1999,
}
@Article{KPM97,
  author = 	 {P. Kirschenhofer and H. Prodinger and C. Mart\'{\i}nez},
  title = 	 {Analysis of {H}oare's {F}IND algorithm with median-of-three partition},
  journal = 	 {Random Structures and Algorithms},
  year = 	 1997,
  volume =	 10,
  pages =	 {143--156}
}
@inproceedings{KPT95,
   author =    {Jyrki Katajainen and Tomi Pasanen and George Titan},
   title =     {Asymptotically efficient in-place merging},
   booktitle = PROC # { 20th Symposium on } # MFCS,
   volume =    969,
   series =    LNCS,
   year =      1995,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {211--220}
}
@article{KPT96,
   author =  {Jyrki Katajainen and Tomi Pasanen and Jukka Teuhola},
   title =   {Practical in-place mergesort},
   journal = njc,
   year =    1996,
   volume =  3,
   pages =   {27--40}
}
@InProceedings{KPT97,
  author = 	 {Jyrki Katajainen and Tomi Pasanen and Jukka Teuhola},
  title = 	 {{T}op-{D}own {N}ot-{U}p {H}eapsort},
  booktitle = {Proceedings of the Algorithm Day in Copenhagen},
  year =	 1997,
  volume = {DIKU Report 97/24}, 
  publisher = {Department of Computing, University of Copenhagen},
  address = {Copenhagen, Denmark},
  pages = {7--9},
}
@article{KRS90,
   author =  {Clyde P. Kruskal and Larry Rudolph and Marc Snir},
   title =   {A complexity theory of efficient parallel algorithms},
   journal = tcs,
   year =    1990,
   volume =  71,
   pages =   {95--132}
}
@inproceedings{KT97,
   author =    {Jyrki Katajainen and Jesper L. Tr\"{a}ff},
   title =     {A meticulous analysis of mergesort programs},
   booktitle = PROC # { 3rd } # ICAC,
   volume =    1203,
   series =    LNCS,
   year =      1997,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {217--228}
}
@article{Kar94,
   author =  {Richard M. Karp},
   title =   {Probabilistic recurrence relations},
   journal = jacm,
   year =    1994,
   volume =  41,
   pages =   {1136--1150}
}
@inproceedings{Kat98,
   author =      {Jyrki Katajainen},
   title =       {The {U}ltimate {H}eapsort},
   booktitle = {Proceedings of the Computing: the 4th Australasian Theory 
   Symposium},
   volume =    {20(3)},
   series =    {Australian Computer Science Communications},
   year =      1998,
   publisher = {Springer-Verlag Singapore Pte. Ltd.},
   address =   {Singapore},
   pages =     {87--95}
}
@article{Kau62a,
   author =  {Kaupe, Jr., Arthur F.},
   title =   {Algorithm 143: {TREESORT} 1},
   journal = cacm,
   year =    1962,
   volume =  5,
   pages =   604
}
@article{Kau62b,
   author =  {Kaupe, Jr., Arthur F.},
   title =   {Algorithm 144: {TREESORT} 2},
   journal = cacm,
   year =    1962,
   volume =  5,
   pages =   604
}
@book{Knu68,
   author =    {Donald E. Knuth},
   series =    {The Art of Computer Programming}, 
   volume =    1,
   title =     {Fundamental Algorithms},
   publisher = {Addison Wesley Longman},
   address =   {Reading, Massachusetts},
   year =      1997,
   edition =   {3rd},
}
@book{Knu69,
   author =    {Donald E. Knuth},
   series =    {The Art of Computer Programming}, 
   volume = 2,
   title =     {Seminumerical Algorithms},
   publisher = {Addison Wesley Longman},
   address =   {Reading, Massachusetts},
   year =      1997,
   edition =   {3rd},
}
@Book{Knu73,
  author = 	   {Donald E. Knuth},
  series =    {The Art of Computer Programming}, 
  volume =    3,
  title =      {Sorting and Searching},
  publisher =  {Addison Wesley Longman},
  address =	   {Reading, Massachusetts},
  year = 	   1998,
  edition =    {2nd},
}
@Book{Knu92,
  author = 	   {Donald E. Knuth},
  series =	 {Lecture Notes in Computer Science},
  volume =	 606,
  title = 	 {Axioms and Hulls},
  publisher = 	 {Springer-Verlag},
  address = {Berlin/\allowbreak{}Heidelberg, Germany},
  year = 	 1992,
}
@Book{Knu93,
  author = 	   {Donald E. Knuth},
  title = 	 {The Standford GraphBase: A Platform for Combinatorial Computing},
  publisher = 	 { Addison-Wesley Publishing Company},
  year = 	 {1993},
  address =	   {Reading, Massachusetts},
}
@article{Kro69,
   author =  {M. A. Kronrod},
   title =   {Optimal ordering algorithm without operational field},
   journal = {Soviet Mathematics},
   year =    1969,
   volume =  10,
   pages =   {744--746}
}
@inproceedings{LL92,
   author =    {Tak Wah Lam and Ka Hing Lee},
   title =     {The implicit dictionary problem revisited},
   booktitle = PROC # { 3rd } # ISAAC,
   volume =    650,
   series =    LNCS,
   year =      1992,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {479--488}
}
@article{LL99,
   author =  {Anthony LaMarca and Richard E. Ladner},
   title =   {The influence of caches on the performance of sorting},
   journal = jalg,
   volume =  31,
   pages =   {66-104},
   year =    1999
}
@article{LP94,
   author =  {Christos Levcopoulos and Ola Petersson},
   title =   {Sorting shuffled monotone sequences},
   journal = infcom,
   volume =  112,
   year =    1994,
   pages =   {37--50}
}
@article{LP96,
   author =  {Christos Levcopoulos and Ola Petersson},
   title =   {Exploiting few inversions when sorting: Sequential and parallel 
              algorithms},
   journal = tcs,
   volume =  163,
   year =    1996,
   pages =   {211--238}
}
@article{LV85,
   author =  {Eugene E. Lindstrom and Jeffrey Scott Vitter},
   title =   {The design and analysis of {B}ucket{S}ort for bubble memory 
              secondary storage},
   journal = ieeetc,
   year =    1985,
   volume =  {C-34},
   pages =   {218--233}
}
@book{LV97,
   author =    {Ming Li and Paul Vit\'{a}nyi},
   title =     {An Introduction to Kolmogorov Complexity and Its Applications},
   publisher = {Springer-Verlag New York, Inc.},
   address =   {New York, New York},
   edition =   {2nd},
   year =      1997,
}
@article{LVW85,
   author =  {Eugene E. Lindstrom and Jeffrey Scott Vitter and C. K. Wong},
   title =   {Introduction---Sorting},
   journal = ieeetc,
   year =    1985,
   volume =  {C-34},
   pages =   {293--295}
}
@inproceedings{LW88,
   author =    {Tony W. Lai and Derick Wood},
   title =     {Implicit selection},
   booktitle = PROC # { 1st } # SWAT,
   volume =    318,
   series =    LNCS,
   year =      1988,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {14--23}
}
@PhdThesis{LaM96,
  author = 	 {Anthony G. LaMarca},
  title = 	 {Caches and Algorithms},
  school = 	 {Department of Computer Science and Engineering, 
                  University of Washington},
  address =      {Seattle, Washington},
  year = 	 1996,
}
@mastersthesis{Lau91,
   author =  {Thomas Lauer},
   title =   {Effiziente {\"U}bersetzung paralleler Programme},
   school =  {Fachbereich Informatik, Universit{\"a}t des Saarlandes},
   address = {Saarbr{\"u}cken, Germany},
   year =    1991
}
@article{M81,
   author =  {R. Melville},
   title =   {A time/space tradeoff for in-place array permutation},
   journal = jalg,
   volume =  2,
   pages =   {139--143},
   year =    1981
}
@article{MEP96,
   author =  {Alistair Moffat and Gary Eddy and Ola Petersson},
   title =   {Splaysort: fast, versatile, practical},
   journal = software,
   volume =  126,
   pages =   {781--797},
   year =    1996
}
@InProceedings{MK95,
  author = 	 {A. Moffat and J. Katajainen},
  title = 	 {In-place calculation of minimum-redundacy codes},
  booktitle = 	 PROC # { 4th } # WADS,
  pages =	 {393-402},
  year =	 1995,
  volume =	 955,
  series =	 LNCS,
  publisher =	 {Springer-Verlag},
  address =   {Berlin/\allowbreak{}Heidelberg, Germany},

}
@article{MP87,
   author =  {J. Ian Munro and Patricio V. Poblete},
   title =   {Searchability in merging and implicit data structures},
   journal = bit,
   year =    1987,
   volume =  27,
   pages =   {324--329}
}
@article{MP92,
   author =  {Alistair Moffat and Ola Petersson},
   title =   {An overview of adaptive sorting},
   journal = acj,
   year =    1992,
   volume =  24,
   pages =   {70--77}
}
@article{MR89,
   author =  {C. J. H. McDiarmid and B. A. Reed},
   title =   {Building Heaps Fast},
   journal = jalg,
   year =    1989,
   volume =  10,
   pages =   {352--365}
}
@inproceedings{MR91,
   author =    {J. Ian Munro and Venkatesh Raman},
   title =     {Sorting multisets and vectors in-place},
   booktitle = PROC # { 2nd } # WADS,
   volume =    519,
   series =    LNCS,
   year =      1991,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {473--480}
}
@article{MR92,
   author =  {J. Ian Munro and Venkatesh Raman},
   title =   {Sorting with minimum data movement},
   journal = jalg,
   year =    1992,
   volume =  13,
   pages =   {374--393}
}
@Book{MR95,
  author = 	 {Rajeev Motwani and Prabhakar Raghavan},
  title = 	 {Randomized Algorithms},
  publisher = 	 {Cambridge University Press},
  address  =     {Cambridge, England},
  year = 	 1995
}
@article{MR96a,
   author =  {J. Ian Munro and Venkatesh Raman},
   title =   {Selection from read-only memory and sorting with minimum data 
              movement},
   journal = tcs,
   year =    1996,
   volume =  165,
   pages =   {311--323}
}
@article{MR96b,
   author =  {J. I. Munro and V. Raman},
   title =   {Fast stable in-place sorting with $O(n)$ data moves},
   journal = algo,
   year =    1996,
   volume =  16,
   pages =   {151--160}
}
@article{MRS90,
   author =  {J. Ian Munro and Venkatesh Raman and Jeffrey S. Salowe},
   title =   {Stable in situ sorting and minimum data movement},
   journal = bit,
   year =    1990,
   volume =  30,
   pages =   {220--234}
}
@article{MS76,
   author =  {Ian Munro and Philip M. Spira},
   title =   {Sorting and searching in multisets},
   journal = sicomp,
   volume =  5,
   year =    1976,
   pages =   {1--8}
}
@article{MS80,
   author =  {J. Ian Munro and Hendra Suwanda},
   title =   {Implicit data structures for fast search and update},
   journal = jcss,
   year =    1980,
   volume =  21,
   pages =   {236--250}
}
@book{MS91,
   author =    {B. M. E. Moret and  H. D. Shapiro},
   title =     {Algorithms from P to NP,
                Volume 1: Design \& Efficiency},
   publisher = {The Benjamin/\allowbreak{}Cummings Publishing Company, Inc.},
   address =   {Redwood City, California},
   year =      1991,
}
@article{MU84,
   author =  {Heikki Mannila and Esko Ukkonen},
   title =   {A simple linear-time algorithm for in situ merging},
   journal = ipl,
   year =    1984,
   volume =  18,
   pages =   {203--208}
}
@article{Man85,
   author =  {Heikki Mannila},
   title =   {Measures of presortedness and optimal sorting algorithms},
   journal = ieeetc,
   year =    1985,
   volume =  {C-34},
   pages =   {318--325}
}
@book{Mel1,
   author =    {Kurt Mehlhorn},
   title =     {Sorting and Searching},
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   year =      1984,
   volume =    1,
   series =    {Data Structures and Algorithms}
}
@article{Mer85,
   author =  {Susan M. Merritt},
   title =   {An inverted taxonomy of sorting algorithms},
   journal = cacm,
   year =    1985,
   volume =  28,
   pages =   {96--99}
}
@article{Mot81,
   author =  {Dalia Motzkin},
   title =   {A {S}table {Q}uicksort},
   journal = software,
   year =    1981,
   volume =  11,
   pages =   {607--611}
}
@article{Mun86,
   author =  {J. Ian Munro},
   title =   {An implicit data structure supporting insertion, deletion, and 
              search in $O(\log^2 n)$ time},
   journal = jcss,
   year =    1986,
   volume =  33,
   pages =   {66--74}
}
@inproceedings{PR98,
   author = {Jakob Pagter and Theis Rauhe},
   title =  {Optimal time-space trede-offs for sorting},
   booktitle = PROC # { 39th } # FOCS,
   year =      1998,
   publisher = {IEEE Computer Society},
   address =   {Los Alamitos, California},
   pages =     {264--268}
}
@Article{PRT83,
  author = 	 {J. T. Postamus and Rinnooy Kan, A. H. G.  and G. T. Timmer},
  title = 	 {An efficient dynamic selection method},
  journal = 	 {Communications of the ACM},
  year = 	 1983,
  volume =	 26,
  pages =	 {878--881}
}
@mastersthesis{Pas93,
   author =  {Tomi Pasanen},
   title =   {Lajittelu minimitilassa},
   school =  {Department of Computer Science, University of Turku},
   address = {Turku, Finland},
   year =    1993
}
@TechReport{Pas96,
  author = 	 {Tomi Pasanen},
  title = 	 {Elementary average case analysis of Floyd's algorithms to construct heaps},
  institution =  {Turku Centre for Computer Science},
  year = 	 1967,
  type =	 {Technical Report},
  number =	 64,
  address =	 {Turku, Finland}
}
@phdthesis{Pet90,
   author =  {Ola Petersson},
   title =   {Adaptive sorting},
   school =  {Department of Computer Science, Lund University},
   address = {Lund, Sweden},
   year =    1990
}
@article{Pre75,
   author =  {F. P. Preparata},
   title =   {A fast stable sorting algorithm with absolutely minimum storage},
   journal = tcs,
   year =    1975,
   volume =  1,
   pages =   {185--190}
}
@Book{RND77,
  author =	 {Edward M. Reingold and J\"{u}rg Nievergelt and Narsingh Deo},
  title = 	 {Combinatorial Algorithms: Theory and Practice},
  publisher = 	 {Prentice-Hall},
  year = 	 1977
}
@phdthesis{Ram91,
   author =  {Venkatesh Raman},
   title =   {Sorting in-place with minimum data movement},
   school =  {Computer Science Department, University of Waterloo},
   address = {Waterloo, Ontario},
   year =    1991
}
@inproceedings{Rei92,
   author =    {Klaus Reinhardt},
   title =     {Sorting \emph{in-place} with a \emph{worst case} complexity of 
                $n\log n - 1.3n+O(\log n)$ comparisons and
		  $\varepsilon\, n \log n  + O(1)$ transports},
   booktitle = PROC # { 3rd } # ISAAC,
   volume =    650,
   series =    LNCS,
   year =      1992,
   publisher = {Springer-Verlag},
   address =   {Berlin/\allowbreak{}Heidelberg, Germany},
   pages =     {489--498}
}
@TechReport{Ros97,
  author = 	 {Laurent Rosaz},
  title = 	 {Improving {K}atajainen's {U}ltimate {H}eapsort},
  institution =  {Department of Computer Science, University of Paris-Sud},
  year = 	 1997,
  type =	 {Report},
  number =	 1115,
  address =	 {Paris, France}
}
@Article{SPP76,
  author = 	 {Arnold Sch\"onhage and Michael S. Paterson and Nicholas Pippenger},
  title = 	 {Finding the Median},
  journal = 	 jcss,
  year = 	 1976,
  volume =	 13,
  pages =	 {184--199}
}
@article{SS87a,
   author =  {Jeffrey Salowe and William Steiger},
   title =   {Simplified stable merging tasks},
   journal = jalg,
   year =    1987,
   volume =  8,
   pages =   {557--571}
}
@article{SS87b,
   author =  {Jeffrey S. Salowe and W. L. Steiger},
   title =   {Stable unmerging in linear time and constant space},
   journal = ipl,
   year =    1987,
   volume =  25,
   pages =   {285--294}
}
@article{SS93,
   author =  {Russel Schaffer and Robert Sedgewick},
   title =   {The analysis of {H}eapsort},
   journal = jalg,
   year =    1993,
   volume =  15,
   pages =   {76--100}
}
@Article{SW84,
  author = 	 {H. W. Six and L. Wegner},
  title = 	 {Sorting a random access file {{\it in situ}}},
  journal =  cj,
  year = 	 1984,
  volume =	 27,
  pages =	 {270--275}
}
@Article{SY80,
  author = 	 {Paul K. Stockmeyer and F. Frances Yao},
  title = 	 {On the optimality of linear merge},
  journal = 	 sicomp,
  year = 	 1980,
  volume =	 9,
  pages =	 {85--90}
}
@phdthesis{Sch92,
   author =  {Russel Warren Schaffer},
   title =   {Analysis of Heapsort},
   school =  {Department of Computer Science, Princeton University},
   address = {Princeton, New Jersey},
   year =    1992
}
@article{Sed77a,
   author =  {Robert Sedgewick},
   title =   {Quicksort with equal keys},
   journal = sicomp,
   year =    1977,
   volume =  6,
   pages =   {240--267}
}
@article{Sed77b,
   author =  {Robert Sedgewick},
   title =   {The analysis of {Q}uicksort programs},
   journal = acta,
   year =    1977,
   volume =  7,
   pages =   {327--355}
}
@article{Sed78,
   author =  {Robert Sedgewick},
   title =   {Implementing {Q}uicksort programs},
   journal = cacm,
   year =    1978,
   volume =  21,
   pages =   {847--857},
   note =    {Corrigendum, \textit{ibidem} \textbf{22} (1979), 368.}
}
@book{Sed80,
   author =    {Robert Sedgewick},
   title =     {Quicksort},
   publisher = {Garland Publishing, Inc.},
   address =   {New York, New York},
   year =      1980
}
@incollection{Sei93,
   author =    {Raimund Seidel},
   title =     {Bacwards analysis of randomized geometric algorithms},
   booktitle = {New Trends in Discrete and Computational Geometry},
   series =    {Algorithms and Combinatorics},
   editor =    {J. Pach},
   volume =    10,
   publisher = {Springer-Verlag},
   address =   {{New York, New York}},
   year =      1993,
   pages =     {37--68}
}
@phdthesis{Sen89,
   author =  {Sandeep Sen},
   title =   {Random sampling tecniques for efficient parallel algorithms in 
              computational geometry},
   school =  {Department of Computer Science, Duke University},
   address = {Durham, North Carolina},
   year =    1989
}
@article{Spr89,
   author =  {Renzo Sprugnoli},
   title =   {The analysis of a simple in-place merging algorithm},
   journal = jalg,
   year =    1989,
   volume =  10,
   pages =   {366--380}
}
@article{Spr96,
   author =  {R. Sprugnoli},
   title =   {Recurrence relations on heaps},
   journal = algo,
   year =    1996,
   volume =  15,
   pages =   {467--480}
}
@book{Str97,
   author =    {Bjarne Stroustrup},
   title =     {The C{\tt ++} Programming Language},
   edition =   {3rd},
   publisher = {Addison-Wesley Publishing Company},
   address =   {Reading, Massachusetts},
   year =      1997,
}
@article{Sym95,
   author =  {Antonios Symvonis},
   title =   {Optimal stable merging},
   journal = cj,
   year =    1995,
   volume =  38,
   pages =   {681--690}
}
@Article{TE91,
  author = 	 {S. Tezuka and P.L Equyer},
  title = 	 {Efficient portable combined Tausworthe random number 
		  generators},
  journal = 	 {ACM. Transactions on Modelling and Computer Simulation},
  year = 	 1991,
  volume =	 { 1},
  pages =	 {99-112}
}
@article{TW,
   author =  {Jukka Teuhola and Lutz Wegner},
   title =   {Minimal space, average linear time duplicate deletion},
   journal = cacm,
   volume =  34,
   number =  3,
   year =    1991,
   pages =   {62--73}
}
@article{Tra77,
   author =  {Trabb Pardo, Luis},
   title =   {Stable sorting and merging with optimal space and time bounds},
   journal = sicomp,
   year =    1977,
   volume =  6,
   pages =   {351--372}
}
@Article{Vit84,
  author = 	 {Jeffrey Scott Vitter},
  title = 	 {Faster methods for random sampling},
  journal =  cacm,
  year = 	 1984,
  volume =	 27,
  pages =	 {703--718}
}
@article{Vui78,
   author =  {Jean Vuillemin},
   title =   {A data structure for manipulating priority queues},
   journal = cacm,
   year =    1978,
   volume =  21,
   pages =   {309--315}
}
@article{W59,
   author =  {P. F. Windley},
   title =   {Transposing matrices in a digital computer},
   journal = cj,
   volume =  2,
   pages =   {47--48},
   year =    1959
}
@Article{WT89,
  author = 	 {L. M. Wegner and J. I. Teuhola},
  title = 	 {The external heapsort},
  journal =  ieeetse,
  year = 	 1989,
  volume =	 15,
  pages =	 {917--925}
}
@article{Weg82,
   author =  {Lutz M. Wegner},
   title =   {Sorting a linked list with equal keys},
   journal = ipl,
   year =    1982,
   volume =  15,
   pages =   {205--208}
}
@article{Weg85,
   author =  {Lutz M. Wegner},
   title =   {Quicksort for equal keys},
   journal = ieeetc,
   year =    1985,
   volume =  {C-34},
   pages =   {362--367}
}
@article{Weg87,
   author =  {Lutz M. Wegner},
   title =   {A generalized, one-way, stackless quicksort},
   journal = bit,
   year =    1987,
   volume =  27,
   pages =   {44--48}
}
@article{Weg92,
   author =  {Ingo Wegener},
   title =   {The worst case complexity of {M}c{D}iarmid and {R}eed's variant 
              of {B}OTTOM-{U}P {H}EAPSORT is less than $n\log n + 1.1n$},
   journal = infcom,
   year =    1992,
   volume =  97,
   pages =   {86--96}
}
@article{Weg93a,
   author =  {I. Wegener},
   title =   {{B}OTTOM-{U}P-{H}EAPSORT, a new variant of {H}EAPSORT beating, on an 
              average, {Q}UICKSORT (if $n$ is not very small)},
   journal = tcs,
   year =    1993,
   volume =  118,
   pages =   {81--98}
}
@article{Weg93b,
   author =  {I. Wegener},
   title =   {A simple modification of {X}unrang and {Y}uzhang's {H}EAPSORT 
              variant improving its complexity significantly},
   journal = cj,
   year =    1993,
   volume =  36,
   pages =   {286--288}
}
@article{Wil64,
   author =  {J. W. J. Williams},
   title =   {Algorithm 232: {H}EAPSORT},
   journal = cacm,
   year =    1964,
   volume =  7,
   pages =   {347--348}
}
@article{Won81,
   author =  {Jin Kue Wong},
   title =   {Some simple in-place merging algorithms},
   journal = bit,
   year =    1981,
   volume =  21,
   pages =   {157--166}
}
@article{XY90,
   author =  {Gu Xunrang and Zhu Yuzhang},
   title =   {A new {H}EAPSORT algorithm and the analysis of its complexity},
   journal = cj,
   year =    1990,
   volume =  33,
   pages =   {281--282}
}
@article{XY94,
   author =  {Gu Xunrang and Zhu Yuzhang},
   title =   {Asymptotic optimal {H}EAPSORT algorithm},
   journal = tcs,
   year =    1994,
   volume =  134,
   pages =   {559--565}
}