SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference

Sorting is a central problem in computer science and one of the key components of many applications. To the best of our knowledge, no reactive programming implementation of sorting algorithms have ever been presented.

In this paper we present a reactive implementation of so-called sorting networks. Sorting networks are networks of comparators that are wired-up in a particular order. Data enters a sorting network along various input wires and leaves the sorting network on the same number of output wires that carry the data in sorted order.

This paper shows how sorting networks can be expressed elegantly in a reactive programming language by aligning the visual representation of a sorting network with the canonical DAG representation of reactive programs. We use our own experimental language called Haai to do so. With a limited number of built-in higher-order reactive programs, we are able to express sorting networks for bubble sort, insertion sort, bitonic sort, pairwise sort and Batcher’s odd-even merge sort.