Insertion Sort (thing)

A sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list. A very innefficient sort (on about the same level of efficiency as the bubble sort).

Example Code:

procedure Insertion( var a : anarray; N : integer);

 var i, j, v : integer;

begin
 
 for i := 2 to N do
  begin
    v := a[i]
    j := i;

      {Short circuit evaluation is assumed for
        the AND in the while loop.}
    while (j > 1) AND (a[j-1] > v) do
     begin
      a[j] := a[j-1]
      j := j-1
     end;

    a[j] := v;

  end;

end;

Back to Sorting Algorithms