Recursive sort that doesn't require list splicing?

Question

I was just wondering if there was some form of sort algorithm that doesn't require any form of splicing of the original list?

Thanks in advance.

Answer 1

A good reference for sorting algorithms is Knuth's Art of Computer Programming vol. 3, Sorting and Searching, 2nd ed.

We will describe two algorithms mentioned in the Comments above. The first of these is "straight insertion sorting", which is Knuth's Program S in Sec. 5.2.1 "Sorting by Insertion". He writes: "This method is extremely easy to implement on a computer; in fact the following [Program S] is the shortest decent sorting routine in this book."

Given an input list L[1..N] of distinct items (for simplicity) and a comparator routine that determines the correct ranking of two items isLess(X,Y) by returning true if X < Y and false if X > Y, we can put the list into a sorted order by calling:

sortListByStraightInsertion(L,N,N)

if the routine sortListByStraightInsertion(L,K,N) is defined as follows:

if (K = 0) then return;   /* else */
M := K;
while ( (M < N) and isLess(L[M+1],L[M]) )
{
    swap(L,M,M+1);  /* transpose Mth and M+1st items in L */
    M := M+1;
}
sortListByStraightInsertion(L,K-1,N);  /* tail recursive call */

Here recursion is being used for the sake of the Question's premise (that recursion should be used) to emulate an iteration. The effect of swap calls within each invocation are to insert L[K] at the proper point in the tail portion of L[K..N] so that it will be in sorted order when the routine calls itself recursively (or returns).

The second algorithm we describe is "bubble sort", which is Knuth's Program B in Sec. 5.2.2 "Sorting by Exchanging", methods that "systematically interchange pairs of elements that are out of order until no more such pairs exist." He further notes that "straight insertion... can be viewed as an exchange method".

Similarly to the above we will frame this "bubble sort" (also known as exchange selection) as a recursive method to be called on a list L[1..N] of distinct items, and "reuse" the comparator isLess and transposer swap already introduced. The the list may be put into sorted order by calling:

sortListByBubbleSort(L,N)

if the routine sortListByBubbleSort(L,N) is defined recursively as:

B := false;
for M := 1 to N-1
{
    if isLess(L[M+1],L[M]) then
    {
        B := true;
        swap(L,M,M+1);
    }
}
if B then sortListByBubbleSort(L,N);  /* recurse, else return */

This algorithm repeatedly scans the list for adjacent items that are out of order and transposes them accordingly, until a final scan reveals that all the items are now in their correct order. The boolean variable B is used to record whether or not an exchange occurs during the present invocation of sortListByBubbleSort. A false value of B indicates no exchange occurred, and thus that the list is now in sort order.