Inserge-Sort: Rewriting Insertion-Sort

This paper presents a novel transposition-based sorting algorithm, which integrates two distinct sorting paradigms, namely Insertion-Sort() and Merge-Sort(). The resulting algorithm, which we call Inserge-Sort(), exhibits several intriguing properties, which are rigorously demonstrated in the paper. Notably, our approach enables fine-grained control over the quantity of inversion pairs in the input array. A simple modification of our algorithm allows for an exact reduction in the number of inversion pairs. It remains to be determined whether other sorting algorithms can be suitably adapted for this purpose. Our algorithm can be thought of as rewriting Insertion-Sort(). The advantage of a rewrite algorithm is that it facilitates the justification of our algorithm's approach while abstracting away implementation details. Additionally, the properties of our algorithm can be established using straightforward inductive arguments. It is also worth noting that adapting traditional sorting algorithms to handle linked list inputs is a non-trivial task, whereas our algorithm can handle such inputs with a minor modification.