  In the age of big data, sorting is an indispensable operation for DBMSes and
similar systems. Having data sorted can help produce query plans with
significantly lower run times. It also can provide other benefits like having
non-blocking operators which will produce data steadily (without bursts), or
operators with reduced memory footprint.
  Sorting may be required on any step of query processing, i.e., be it source
data or intermediate results. At the same time, the data to be sorted may not
fit into main memory. In this case, an external sort operator, which writes
intermediate results to disk, should be used.
  In this paper we consider an external sort operator of the comparison-based
sort type. We discuss its implementation and describe related design decisions.
Our aim is to study the impact on performance of a data structure used on the
merge step. For this, we have experimentally evaluated three data structures
implemented inside a DBMS.
  Results have shown that it is worthwhile to make an effort to implement an
efficient data structure for run merging, even on modern commodity computers
which are usually disk-bound. Moreover, we demonstrated that using a loser tree
is a more efficient approach than both the naive approach and the heap-based
one.
