Direct Insertion Sort Algorithm void Insertion Sort( ElementType A[], int N) ElementType Tmp; for(P=1;P≤N;P++){ Tmp=A[P]: the next coming card*/ for(j=P; j>0&&A[j-1]> Tmp; j-) A[j]=A[j-1]; shift sorted cards to provide a position for the new coming card"/ A[j]= Tmp;/ place the new card at the proper position*/ 3 /end for-P-loop * The worst case: Input al is in reverse order. T(N)=O(N2) The best case: Input al is in sorted order. T(N)=O(N)Direct Insertion Sort Algorithm void InsertionSort ( ElementType A[ ], int N ) { int j, P; ElementType Tmp; for ( P = 1; P < N; P++ ) { Tmp = A[ P ]; /* the next coming card */ for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) A[ j ] = A[ j - 1 ]; /* shift sorted cards to provide a position for the new coming card */ A[ j ] = Tmp; /* place the new card at the proper position */ } /* end for-P-loop */ } The worst case: Input A[ ] is in reverse order. T( N ) = O( N2 ) The best case: Input A[ ] is in sorted order. T( N ) = O( N )