Delphi.
unit USmoothsort;
interface
procedure SmoothSort(var A: array of TItem);
implementation
function IsAscending(v1,v2: TItem): boolean;
begin
 result := v1<=v2;
end;
procedure SmoothSort(var A: array of TItem);
var q,r,
 p,b,c,
 r1,b1,c1,
 N: integer;
 procedure up(var vb,vc: integer);
 var temp: integer;
 begin
 temp := vb;
 vb := vb+vc+1;
 vc := temp;
 end;
 procedure down(var vb,vc: integer);
 var temp: integer;
 begin
 temp := vc;
 vc := vb-vc-1;
 vb := temp;
 end;
 procedure sift;
 var r0, r2: integer;
 T: TItem;
 begin
 r0 := r1;
 T := A[r0];
 while b1>=3 do
 begin
 r2 := r1-b1+c1;
 if not IsAscending(A[r1-1],A[r2]) then
 begin
 r2 := r1-1;
 down(b1,c1);
 end;
 if IsAscending(A[r2],T) then b1 := 1 else
 begin
 A[r1] := A[r2];
 r1 := r2;
 down(b1,c1);
 end;
 end;
 if r1<>r0 then A[r1] := T;
 end;
 procedure trinkle;
 var p1,r2,r3, r0 : integer;
 T: TItem;
 begin
 p1 := p; b1 := b; c1 := c;
 r0 := r1;
 T := A[r0];
 while p1>0 do
 begin
 while (p1 and 1)=0 do
 begin
 p1 := p1 shr 1; up(b1,c1);
 end;
 r3 := r1-b1;
 if (p1=1) or IsAscending(A[r3],T) then p1 := 0 else
 begin
 p1 := p1 - 1;
 if b1=1 then
 begin
 A[r1] := A[r3];
 r1 := r3;
 end else
 if b1>=3 then
 begin
 r2 := r1-b1+c1;
 if not IsAscending(A[r1-1],A[r2]) then
 begin
 r2 := r1-1;
 down(b1,c1); p1 := p1 shl 1;
 end;
 if IsAscending(A[r2],A[r3]) then
 begin
 A[r1] := A[r3];
 r1 := r3;
 end else
 begin
 A[r1] := A[r2];
 r1 := r2;
 down(b1,c1); p1 := 0;
 end;
 if r0<>r1 then A[r1] := T;
 sift;
 end;
 procedure semitrinkle;
 var T: TItem;
 begin
 r1 := r-c;
 if not IsAscending(A[r1],A[r]) then
 begin
 T := A[r];
 A[r] := A[r1];
 A[r1] := T;
 trinkle;
 end;
 end;
begin
 N := length(A);
 q := 1; r := 0;
 p := 1; b := 1; c := 1;
 //building tree
 while q < N do
 begin
 r1 := r;
 if (p and 7) = 3 then
 begin
 b1 := b; c1 := c; sift;
 p := (p+1) shr 2; up(b,c); up(b,c);
 end
 else if (p and 3) = 1 then
 begin
 if q + c < N then
 begin
 b1 := b; c1 := c; sift;
 end else trinkle;
 down(b,c); p := p shl 1;
 while b > 1 do
 begin
 down(b,c); p := p shl 1;
 end;
 p := p+1;
 end;
 q := q + 1; r := r + 1;
 end;
 r1 := r; trinkle;
 //bulding sorted array
 while q>1 do
 begin
 q := q - 1;
 if b = 1 then
 begin
 r := r - 1;
 p := p - 1;
 while (p and 1) = 0 do
 begin
 p := p shr 1; up(b,c);
 end;
 end else
 if b >= 3 then
 begin
 p := p - 1; r := r-b+c;
 if p > 0 then semitrinkle;
 down(b,c); p := p shl 1 + 1;
 r := r+c; semitrinkle;
 down(b,c); p := p shl 1 + 1;
 end;
 //element q is done
 end;
 //element 0 is done
end;
end.
C#.
Implémentation accompagnée de petits exemple pour l'optimiser en fonction de structure particulière
using System;
using System.Collections.Generic;
using System.Text;
namespace NitsujMoteur
 #region comparaisons
 public struct elem_indicéf
 public float indice;
 public object elem;
 public int indiceOrig;//n'est pas rempli par le code, optionnel si besoin est.
 public class indicef_comparer : IComparer<elem_indicéf>
 #region IComparer<elem_indicéf> Membres
 int IComparer<elem_indicéf>.Compare(elem_indicéf x, elem_indicéf y)
 if (x.indice < y.indice)
 return -1;
 else if (x.indice > y.indice)
 return 1;
 else
 return 0;
 //return x.indice - y.indice;
 #endregion
 public struct elem_indicé
 public int indice;
 public object elem;
 public int indiceOrig;//n'est pas rempli par le code, optionnel si besoin est
 public class indice_comparer : IComparer<elem_indicé>
 #region IComparer<elem_indicé> Membres
 int IComparer<elem_indicé>.Compare(elem_indicé x, elem_indicé y)
 return x.indice - y.indice;
 #endregion
 public class int_comparer : IComparer<int>
 #region IComparer<int> Membres //public car dans l'interface...
 int IComparer<int>.Compare(int x, int y)
 return x - y;
 #endregion
 #endregion
 public class Trie<T, TC> where TC : IComparer<T>
 /* An algorithm developed by Edsger Dijkstra based on the same principle as
 * heapsort. By using a postorder traversal of a heap-like structure, O(n)
 * time complexity is achieved for already-sorted data.
 * Time complexity:
 * O(n log n) worst case
 * O(n) best case
 * Working memory:
 * O(1) all cases
 private static void up(ref int b, ref int c)
 int temp = b + c + 1;
 c = b;
 b = temp;
 private static void down(ref int b, ref int c)
 int temp = b - c - 1;
 b = c;
 c = temp;
 private static void sift(int r, int b, int c, T[] data, TC Comp)
 while (b >= 3)
 int r2 = r - b + c;
 if (Comp.Compare(data[r2], data[r - 1]) < 0)//data[r2] < data[r - 1])
 r2 = r - 1;
 down(ref b, ref c);
 if (Comp.Compare(data[r], data[r2]) >= 0)//data[r] >= data[r2])
 b = 1;
 else
 swap(ref data[r], ref data[r2]);
 r = r2;
 down(ref b, ref c);
 private static void trinkle(int r, int p, int b, int c, T[] data, TC Comp)
 while (p > 0)
 int r3;
 while (p % 2 == 0)
 p /= 2;
 up(ref b, ref c);
 r3 = r - b;
 if (p == 1 || Comp.Compare(data[r3], data[r]) <= 0)//data[r3] <= data[r])
 p = 0;
 else
 p--;
 if (b == 1)
 swap(ref data[r], ref data[r3]);
 r = r3;
 else if (b >= 3)
 int r2 = r - b + c;
 if (Comp.Compare(data[r2], data[r - 1]) < 0)//data[r2] < data[r - 1])
 r2 = r - 1;
 down(ref b, ref c);
 p *= 2;
 if (Comp.Compare(data[r3], data[r2]) >= 0)//data[r3] >= data[r2])
 swap(ref data[r], ref data[r3]);
 r = r3;
 else
 swap(ref data[r], ref data[r2]);
 r = r2;
 down(ref b, ref c);
 p = 0;
 sift(r, b, c, data, Comp);
 private static void semitrinkle(int r, int p, int b, int c, T[] data, TC Comp)
 int r1 = r - c;
 if (Comp.Compare(data[r1], data[r]) > 0)//data[r1] > data[r])
 swap(ref data[r], ref data[r1]);
 trinkle(r1, p, b, c, data, Comp);
 private static void swap(ref T x, ref T y)
 T temp = x;
 x = y;
 y = temp;
 public static void smoothSort(T[] data, TC Comp)
 if (data.Length <= 1)
 return;
 int q = 1, r = 0, p = 1, b = 1, c = 1;
 while (q != data.Length)
 if (p % 8 == 3)
 sift(r, b, c, data, Comp);
 p = (p + 1) / 4;
 up(ref b, ref c); up(ref b, ref c);
 else if (p % 4 == 1)
 if (q + c < data.Length)
 sift(r, b, c, data, Comp);
 else
 trinkle(r, p, b, c, data, Comp);
 do
 down(ref b, ref c);
 p *= 2;
 } while (b != 1);
 p++;
 q++; r++;
 trinkle(r, p, b, c, data, Comp);
 while (q != 1)
 q--;
 if (b == 1)
 r--; p--;
 while (p % 2 == 0)
 p /= 2;
 up(ref b, ref c);
 else if (b >= 3)
 p--;
 r += c - b;
 if (p != 0) semitrinkle(r, p, b, c, data, Comp);
 down(ref b, ref c);
 p = 2 * p + 1;
 r += c;
 semitrinkle(r, p, b, c, data, Comp);
 down(ref b, ref c);
 p = 2 * p + 1;
 #region spécialisation
 public class Trie_elem_indicéf : Trie<elem_indicéf, indicef_comparer>
 public static void smoothSort(elem_indicéf[] data)
 smoothSort(data, new indicef_comparer());
 public class Trie_elem_indicé : Trie<elem_indicé, indice_comparer>
 public static void smoothSort(elem_indicé[] data)
 smoothSort(data, new indice_comparer());
 #endregion

Implémentation d'algorithmes classiques/Algorithmes de tri/Tri de Shell