Overview

Let $n\ge 0$. The sorting problem refers to permuting records $a_1,a_2,\dots ,a_n$ into a new sequence $⟨a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }⟩$ such that $key(a_1^{\prime })\le key(a_2^{\prime })\le \cdots \le key(a_n^{\prime })$.

A few key terms are used to describe properties of sorting algorithms:

• Stability
  • An algorithm is stable if values that compare as equal are ordered the same in the output as they are in the input.
• In Place
  • An algorithm is in place if only a constant number of input values are ever stored outside the array.
• Adaptive
  • An algorithm is adaptive if it takes advantage of existing order in its input.

Structural Comparison

Theelixir documentation makes a point that there exist two types of comparisons between data types.¹ The first is structural in which comparisons are made on the underlying data structures used to describe the data types. The second is semantic which focuses on making the comparison with respect to what the data types represent.

iex> 1 < :atom  # structural
true
iex> Date.compare(~D[2017-03-31], ~D[2017-04-01])  # semantic
:lt

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, 3rd ed (Cambridge, Mass: MIT Press, 2009).
• “Kernel — Elixir v1.16.1,” accessed February 2, 2024, https://hexdocs.pm/elixir/1.16/Kernel.html#module-structural-comparison.