# Recursive sort that doesn't require list splicing?

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

• What does "splicing" mean in this context? Straight insertion sort, sometimes described as the "first decent sorting algorithm", proceeds by constructing the sorted output without necessarily changing the input list. However entries from the original list are inserted one at a time into the output list. Also algorithms such as the infamous "bubble sort" proceed by comparing and possibly transposing adjacent elements in the original list. Does this constitute "splicing"? – hardmath Oct 18 '14 at 15:15
• Just no splitting up of the original list into smaller pieces at all. (think merge sort) – Akatzki Oct 18 '14 at 16:29
• So bubble sort (transposing adjacent elements) is allowed? – hardmath Oct 18 '14 at 17:30
• yes, that's what I was thinking. However i'm not sure how to approach that. – Akatzki Oct 18 '14 at 18:54
• If I may ask, how does the requirement of a "recursive sort" figure in your problem? A natural use of recursion is to solve a "big" problem by combining the solutions of smaller problems. Sorting can be done in many ways, some more efficient than others. Merge sort is not the only algorithm, and almost any algorithm that exists can be artificially construed as a recursive one (even if a more natural presentation is an iterative one). – hardmath Oct 18 '14 at 20:07

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.