Sorting:

Sorting algorithm is an algorithm that puts elements of a list in a certain order . The most-used orders are numerical order and lexicographical order.

Sorting algorithm classification:

Computaional complexcity.

Memory utilization

Stability-Maintaining relative order of records with equal keys.

No.of comparisions

Methods applied like insertion,exchange,,selection,merging etc.

Sorting is a process of linear ordering of list of objects

Sorting techniques are categoried into:

1. Internal sorting

2. External sorting

Internal sorting:

           It takes the place in the main memory of a computer.

                 Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc

External sorting:

It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory

                Eg:Merge sort,Multiway Merge,Polyphase merge.

Insertion Sort:
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort , heapsort, or merge sort.
                                    (or)

Insertion sorts works by taking elements from the list one by one and inserting them in their current position into a new sorted list.

Insertion sort consists of N-1 passes.

Insertion Sort Provides Several Advantages:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O( n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e. O ( n 2)) algorithms such as selection sort or bubble sort: the average running time is n 2/4, and the running time is linear in the best case
• Stable, i.e. does not change the relative order of elements with equal keys
• In-place , i.e. only requires a constant amount O(1) of additional memory space
• Online , i.e. can sort a list as it receives it

Limitations of insertion sort:

          It is relatively efficient for small lists and mostly- sorted list.

          It is expensive because of shifting all following elements by one.

Analysis of  insertion sort:

Worest case performance O(n2)

Best case performance O(n)

Average case performance O(n2)    

Algorithm steps:

                   Step 1: Read the input list size.

                   Step 2: Read the list elements.

                   step 3:  pass=1

                   step 4:  Repeat the following steps until pass reach size-1 (for N-1 passes)

                         i)   key=list[Pass]

                         ii)   swap=pass-1

                         iii) Repeat the follwoing steps if this condition is true list[swap]>key and                              swap >= 0.(for comparision).

                                    a) list [sawp+1]=list[swap ]

                                    b) swap--

C Program To Implement Insertion Sort

CPP Program To Insertion Sort