[Pascal language] Recursion within a Shell Sort

Definition

Recursion, in the computing or mathematical terms, is a method of defining functions in which the function being defined is applied within its own designation. The term is also used more generally to describe the process of repeating objects in a similar pattern.

Implementation

Here below you will find a simple recursive procedure allowing you to sort a table of (n) number of integers using the Shell sorting method:

Procedure Shell_Sort_Rec (Var t: TAB; n,h : integer); 
Var aux,i : integer; 
begin 
    If h > 0 Then 
    Begin 
        If n > h Then 
             begin 
                  Shell_Sort_Rec (t,n - h,h); 
                  If t[n] < t[n - h] Then 
                  Begin 
                     aux:= t[n]; 
                     i := n; 
                     Repeat                         
                        t[i] := t[i - h]; 
                        i := i - h; 
                     Until (i = h) Or (aux > t[i - h]); 
                     t[i] := aux; 
                  End; 
              End; 
        Shell_Sort_Rec (t,n,h Div 3); 
    End; 
End;

Notes

It is better to test this procedure on small tables, because in the case that the number of calls becomes too important may spillover the limits of the memory stack allocate to recursive function. You can increase the size of the test table on increasing the size of the stack:

OptioncompilerMemory Settingsstack size 

• Learn more about the Shell Sort Algorithm
• Thanks to Zouari Lazhar for this tip