Adapted 2-phase 2-band mixing

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

The 2-phase 2-band mixing is a sort algorithm .

more details

In the early days of electronic data processing , mass data was stored on magnetic tapes . These tapes were sequentially read and written with a magnetic head. So no random access was possible. One made do with algorithms that sequentially sorted a tape with the help of a second (possibly also a third).

This procedure was adapted for doubly linked lists at the end of the 1990s ( Markus v. Brevern and Dirk Sorges ).

Doubly linked lists consist of list elements that have a pointer to the successor and to the predecessor. So you can run through the lists from the beginning forwards or from the end backwards. Inserting and deleting is very easy. A list is clearly superior to a field in these two operations.

In 2-phase-2-band mixing, runs of sorted elements are determined in one phase . These runs are then mixed together in the second phase, so that 2 runs become one. The algorithm ends when there is only one (now fully sorted) run left.

In the case of doubly linked lists, the forward pointers are used as pointers to the next element and the backward pointers as pointers to the next run. The list is initialized by making the backward pointers for each element point to the next element like the forward pointers. Now you have n runs of length 1. Then you sort two runs together until only one run is left. Sorting can be achieved with two additional pointers, each of which points to a run. The smaller referenced element is included in the mixed run, the corresponding pointer is set to the next element of the run. Once a run has been completed, the rest of the other run is added to the mixed run. Appending and sorting is achieved simply by “moving around”. Finally, all backward pointers are set to the previous element.

This process works in-place , so it does not require any additional storage space. Nothing is copied, only the pointers are changed. The effort is always O (n * log n). So it is the perfect sorting method for indefinite data.