Insertion Sort works on the fundamental effort to turn the given the unsorted list into a ordered list. So before describing the Insertion Sort itself, we'll look a bit at the fundamental of the Ordered List.
The Concept - Ordered List
Ordered List is a data-structure which is defined as a list in which every entry contains a key, such that the keys are in order.
Thus if an entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j. Thus the entries i and j are ordered in the list.
Ordered Insertion forms the fundamental idea behind the Insertion Sort. Insertion mechanism into the Ordered List may be termed as Ordered Insertion. The whole idea revolves around the effort to convert the unordered list into the ordered list. The elements can be inserted in the ordered list by Ordered Insertion.
Given an Ordered List L, if we wish to insert a new entry e, then the following steps need to be followed:
- Find the correct Location in the list L where the entry e belongs. Thus Location(e) in L will be such that, all elements of L before Location(e) will be less that e and all elements of L after Location(e) will be greater than e.
- Insert the entry at Location(e) in the list L.
