Insertion Sorting using Data Structure
• This sorting divides the list into sorted part and unsorted parts.
• It picks up one one element from the front of the unsorted part and inserts it at its proper place in the sorted path.
• This step repeats till the unsorted part is exhausted.
• Now we pick up the element from the front of the unsorted part.
• When we try to insert this element in sorted part, we find that the element in the sorted part(i.e 8) will have to be shifted one place towards right to accommodate the incoming elements.
• This insertion process is repeated in the unsorted part is exhausted.
Scan the shortest path to find the place where the element to be inserted and while scanning shift the element to the next part to create space.