@PhdThesis{chaudhry:thesis,
  author = {Geeta Chaudhry},
  title = {Parallel Out-of-Core Sorting: The Third Way},
  year = {2004},
  month = {September},
  number = {TR2004-517},
  institution = {Dartmouth College, Computer Science},
  school = {Dartmouth College},
  address = {Hanover, NH},
  note = {Available as Dartmouth Technical Report TR2004-517},
  URL = {https://digitalcommons.dartmouth.edu/dissertations/7/},
  keywords = {out-of-core sorting, columnsort, cluster computing, parallel I/O,
  pario-bib},
  abstract = {Sorting very large datasets is a key subroutine in almost any
  application that is built on top of a large database. Two ways to sort
  out-of-core data dominate the literature: merging-based algorithms and
  partitioning-based algorithms. Within these two paradigms, all the programs
  that sort out-of-core data on a cluster rely on assumptions about the input
  distribution. We propose a third way of out-of-core sorting: oblivious
  algorithms. In all, we have developed six programs that sort out-of-core data
  on a cluster. The first three programs, based completely on Leighton's
  columnsort algorithm, have a restriction on the maximum problem size that
  they can sort. The other three programs relax this restriction; two are based
  on our original algorithmic extensions to columnsort. We present experimental
  results to show that our algorithms perform well. To the best of our
  knowledge, the programs presented in this thesis are the first to sort
  out-of-core data on a cluster without making any simplifying assumptions
  about the distribution of the data to be sorted.},
  comment = {Doctoral dissertation. Advisor: Thomas H. Cormen}
}