template
     
       //Insertion Sort void inssort(Elem A[],int n) {
        for(int i=1;i
      
       0)&&(Comp::lt(A[j],A[j-1]));j--)             swap(A,j,j-1); } //Bubble Sort template
       
         void bubsort(Elem A[],int n) {
        for(int i=0;i
        
         i;j--)             if(Comp::lt(A[j],A[j-1]))                 swap(A,j,j-1); } //Selection Sort template 
         
           void selsort(Elem A[],int n) {
        for(int i=0;i
          
           i;j--) if(Comp::lt(A[j],A[lowindex])) lowindex=n; swap(A,i,lowindex); } } //Modified version of Insertion Sort for varying increments template
           
             void inssort2(Elem A[],int n,int incr) { for(int i=incr;i
            
             =incr)&&(Comp::lt(A[j],A[j-incr]));j-=incr) swap(A,j,j-incr); } //ShellSort template
             
               void shellsort(Elem A[],int n) { for(int i=n/2;i>2;i/=2) for(int j=0;j
              
               (&A[j],n-j,i); inssort2
               
                (A,n,1); } //QuickSort template
                
                  void qsort(Elem A[],int i,int j) { if(j<=i) return; int pivotindex=findpivot(A,i,j); swap(A,pivotindex,j); int k=partition
                 
                  (A,i-1,j,A[j]); swap(A,k,j); qsort
                  
                   (A,i,k-1); qsort
                   
                    (A,k+1,j); } template 
                    
                      int findpivot(Elem A[],int i,int j) { return (i+j)/2; } template 
                     
                       int partition(Elem A[],int l,int r,Elem& pivot) { do { while(Comp::lt(A[++l],pivot)) while((r!=0)&&Comp::gt(A[--r],pivot)); swap(A,l,r); }while(l
                      
                        void mergesort(Elem A[],Elem temp[],int left,int right) { int mid=(left+right)/2; if(left==right) return; mergesort
                       
                        (A,temp,left,mid); mergesort
                        
                         (A,temp,mid+1,right); for(int i=left;i<=right;i++) temp[i]=A[i]; //Do the merge operation back to A int i1=left; int i2=mid+1; for(int curr=left;curr<=right;curr++) { if(i1==mid+1) A[curr]=temp[i2+1]; else if(i2>right) A[curr]=temp[i1++]; else if(Comp::lt(temp[i1],temp[i2])) A[curr]=temp[i1++]; else A[curr]=temp[i2++]; } } template
                         
                           void mergesort(Elem A[],Elem temp[],int left,int right) { if((right-left)<=THRESHOLD) { inssort
                          
                           (&A[left],right-left+1); return; } int i,j,k,mid=(left+right)/2; if(left==right) return; mergesort
                           
                            (A,temp,left,mid); mergesort
                            
                             (A,temp,mid+1,right); //Do the merge operation ,First,copy 2 halves to temp for(i=mid;i>=left;i--) temp[i]=A[i]; for(j=1;j<=right-mid;j__) temp[right-j+1]=A[j+mid]; for(i=left,j=right,k=left;k<=right;k++) if(temp[i]
                             
                               void heapsort(Elem A[],int n) { Elem mval; maxheap
                              
                                H(A,n,n); for(int i=0;i