# Insertion Sort

Insertion sort is more efficient than bubble sort and it is easy to understand and code.

To achieve an insertion sort you begin to build up an ascending sorted list by comparing the second item of the unsorted list with the first. If the second item is less, insert it before the first. Now the first two items of the new list are in the correct order. Next, compare the third item of the unsorted list with the second item of the new list. If the third item is less, put second item into the third position to make room for an insertion. Now compare the third item with the first. If the third is greater, put it into the vacant second position in the array. If it is less, 'promote' the first item into the vacant slot and place the newest item in the first position. Similarly, the compare as necessary the other items in the unsorted list with the items already present in the sorted list and insert them appropriately. The output of the demonstration program should make this clear. The first five items of a 16-item array are sorted as follows:

```Initial array:
503  87 512  61 908 170 897 275 653 426 154 509 612 677 765 703

Sorted up to index 2. 87 inserted at position 1:
87 503 512  61 908 170 897 275 653 426 154 509 612 677 765 703

Sorted up to index 3. 512 inserted at position 3:
87 503 512  61 908 170 897 275 653 426 154 509 612 677 765 703

Sorted up to index 4. 61 inserted at position 1:
61  87 503 512 908 170 897 275 653 426 154 509 612 677 765 703

Sorted up to index 5. 908 inserted at position 5:
61  87 503 512 908 170 897 275 653 426 154 509 612 677 765 703```

We have added a Smart Pascal web version outputting the complete sort following this Pascal code.

```program InsertionSortDemo;
{\$Apptype Console}
const
UPPER_BOUND = 16;
var
Nums : array[1 .. UPPER_BOUND] of integer =  (503, 087, 512, 061, 908,
170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703);
procedure Display;
var
Count : integer;
begin
for Count := 1 to UPPER_BOUND do
write(Nums[Count] : 4);
writeln;
end;

procedure InsertionSort;
var
Inserted : Boolean;
Current, Insert, Temp : integer;
begin
if UPPER_BOUND < 2 then
writeln('No sorting possible')
else
begin
for Insert := 2 to UPPER_BOUND do
begin
Inserted := False;
Current := Insert;
Temp := Nums[Insert];
while not inserted do
begin
if Temp > Nums[Current - 1] then
begin
Inserted := True; // Position found;
Nums[Current] := Temp;
writeln(#13#10,'Sorted up to index ', Insert,
'. ', Temp,' inserted at position ', Current,':');
Display;
end
else
begin
// Shift up integer one place
Nums[Current] := Nums[Current - 1];
dec(Current);
if Current = 1 then
begin
Nums[1] := Temp;
writeln(#13#10,'Sorted up to index ', Insert,
'. ', Temp, ' inserted at position 1:');
Inserted := True;
Display;
end;
end;
end;//while
end;//for
end;//if
end;//proc

begin
writeln('Initial array:');
Display;
InsertionSort;
readln;
end.

```

## Smart Pascal Console Demonstration

If the output fails to show in your current browser, try another such as Chrome.

## Smart Pascal Code of Insertion Sort

```unit Unit1;

interface

uses
System.Types, System.Lists, SmartCL.System, SmartCL.Scroll, SmartCL.Console,
SmartCL.Components, SmartCL.Application, SmartCL.ConsoleApp;

type
TApplication = class(TW3CustomConsoleApplication)
private
const UPPER_BOUND = 16;
const FIELD_WIDTH = 4;
Nums : array[1 .. 16] of integer =  [503, 087, 512, 061, 908, 170, 897, 275,
653, 426, 154, 509, 612, 677, 765, 703];
protected
procedure PopulateConsole; override;
procedure Display;
procedure InsertionSort;
end;

implementation

procedure TApplication.Display;
begin
var strNums = '';
for var Count := 1 to UPPER_BOUND do
begin
var strNum := inttostr(Nums[Count]);
for var i := 1 to FIELD_WIDTH - length(strNum) do
strNum := '&nbsp;' + strNum;
strNums += strNum;
end;
Console.writeln(strNums);
end;

procedure TApplication.InsertionSort;
var
Inserted : Boolean;
Current, Insert, Temp : integer;
begin
if UPPER_BOUND < 2 then
writeln('No sorting possible')
else
begin
for Insert := 2 to UPPER_BOUND do
begin
Inserted := False;
Current := Insert;
Temp := Nums[Insert];
while not inserted do
begin
if Temp > Nums[Current - 1] then
begin
Inserted := True; // Position found;
Nums[Current] := Temp;
Console.writeln(#13#10 + 'Sorted up to index ' + intToStr(Insert) +
'. ' + intToStr(Temp) + ' inserted at position ' + intToStr(Current) + ':');
Display;
end
else
begin
// Shift up integer one place
Nums[Current] := Nums[Current - 1];
dec(Current);
if Current = 1 then
begin
Nums[1] := Temp;
Console.writeln(#13#10 + 'Sorted up to index ' + intToStr(Insert) +
'. ' + intToStr(Temp) +  ' inserted at position 1:');
Inserted := True;
Display;
end;
end;
end;//while
end;//for
end;//if
end;//proc

procedure TApplication.PopulateConsole;
begin
Console.writeln('Initial array:');
Display;
InsertionSort;
end;

end.

```
Programming - a skill for life!

Bubble sort, insertion sort, tree sort and quicksort