• Comparison Sort
  1. Selection Sort
     • advantages: least data movement (N – 1 exchanges).
     • disadvantages: does not make good use of the initial order of the keys, and one pass through the keys does not give any hint to the next pass.
     • stability: stable.
     • operations: N²/2 comparisons, N – 1 exchanges.
     • space: in-space sort, O(N).
     • implementation in C:

       void selection_sort(Item a[], int l, int r)
       {
         int i, j;
         for (i = l; i < r; ++i)
         {
           int min = i;
           for (j = i + 1; j <= r; ++j)
             if (less(a[j], a[min])) min = j;
           exch(a[i], a[min]);
         }
       }
                                

  2. Insertion Sort
     • advantages: make good use of the initial order of the keys, so efficient for partially sorted sequences; uses much fewer comparisons than selection sort and bubble sort.
     • disadvantages:
     • stability: stable.
     • operations: the running time is proportional to the total number of inversions in the sequence, and is irrelevant of the distribution of the inversions.
       • best case: N comparisons, no movement.
       • average case: N² / 4 comparisons, N² / 4 movements.
       • worse case: N² / 2 comparisons, N² / 2 movements.
     • space: in-space sort, O(N).
     • implementation in C:

       void insertion_sort(Item a[], int l, int r)
       {
         int i;
         /* find the minimun first to use as a sentinel */
         for (i = l + 1; i <= r; ++i)
           compexch(a[l], a[i]);
         for (i = l + 2; i <= r; ++i)
         {
           int j = i;
           Item v = a[i];
           while (less(v, a[j - 1]))
           {
             a[j] = a[j - 1];
             --j;
           }
           a[j] = v;
         }
       }
       

  3. Bubble Sort
     • advantages: efficient for one type of partially sorted sequences which has few right inversions corresponding to each element, such as a new sequence built from a sorted sequence by appending a few elements.
     • disadvantages: slowest in most cases.
     • stability: stable.
     • operations: the number of passes through the sequence during sorting is equal to the maximum number of right inversions corresponding to one element.
       • best case: O(N²) comparisons(can be reduced to N by tracing whether the sequence is already in order), no movement.
       • average case: O(N²) comparisons, N² / 4 exchanges(can be reduced to N² / 4 movements).
       • worst case: O(N²) comparisons, N² / 2 exchanges(can be reduced to N² / 2 movements).
     • space: in-space sort, O(N).
     • implementation in C:

       void bubble_sort(Item a[], int l, int r)
       {
         int i, j;
         for (i = l; i < r; ++i)
           for (j = r; j > i; --j)
             compexch(a[j-1], a[j]);
       }
                   

  4. Shell Sort
     • advantages: extension of insert sort with more effective(long distance) movements; insensitive to the input.
     • disadvantages: hard to analyze the running time and to choose a best increment sequence; bad increment sequences exist.
     • stability: stable.
     • operations:
       • less than O(N^3/2) comparisons for the increments 1 4 13 40 121 364 1093 3280 9841 ... (s(i+1) = s(i) * 3 + 1)
       • less than O(N^4/3) comparisons for the increments 1 8 23 77 281 1073 4193 16577 ... (s(i) = 4ⁱ + 3*2ⁱ + 1)
       • less than O(Nlog²N) comparisons for the increments 1 2 3 4 6 9 8 12 18 27 16 24 36 54 81 ...
         (that is Pratt increment sequence: each number in the triangle is two times the number above and to the right of it and also three times the number above and to the left of it.

                  1
         
                2   3
         
              4   6   9
         
           8   12   18  27
         
         16  24   36   54  81
                         

         )

     • space: in-space sort, O(N).
     • implementation in C:

       /* increment sequence: 1 4 13 40 121 364 1093 3280 9841 ... */
       void shell_sort(Item a[], int l, int r)
       {
         int i, j, h;
         for (h = 1; h <= (r - l) / 9; h = 3 * h + 1) ;
         for ( ; h > 0; h /= 3)
           for (i = l + h; i <= r; ++i)
           {
             int j = i;
             Item v = a[i];
             while (j >= l + h && less(v, a[j - h]))
             {
               a[j] = a[j-h];
               j -= h;
             }
             a[j] = v;
           }
       }
                   

  5. Quick Sort
     • advantages: has extremely short inner loop, thus small constant factor; has been thoroughly analyzed, extensively verified, wisely refined, thus can be widely used in a broad variety of practical sorting applications.
     • disadvantages: little mistakes in the implementation easily go unnoticed and badly impair the performance for some sequences; sensitive to input, thus worst case can not be completely avoided.
     • stability: unstable.
     • operations:
       • best case: NlgN comparisons.
       • average case: 2NlnN comparisons.
       • worse case: N² / 2 comparisons.
     • space: in-space sort, O(N) + O(N)(taken by recursion stack, can be reduced to O(lgN) by first sorting the smaller subsequence and tail-recursion removal).
     • implementation in C:

       void sort(Item a[], int l, int r)
       {
         quick_sort(a, l, r);
         /* refinement 1: insertion sort is efficient for the almost sorted
          * file left by the prudent quick sort */
         insertion_sort(a, l, r);
       }
       
       void quick_sort(Item a[], int l, int r)
       {
         int i, j;
       
         stackinit();
         push2(l, r);
         while (!stackempty())
         {
           l = pop();
           r = pop();
           /* refinement 1: use cutoff for small subfiles to limit the number
            * of small problems at deep recursion, thus to save a major part
            * of recursive subroutine call overhead */
           if (r-1 < M) continue;
           partition(a, l, r, &i, &j);
           /* refinement 2: use explicit pushdown stack to do tail-recursion
            * removal, and sort small subfile first to reduce the maximum stack depth */
           if (i-l > r-i) {
             push2(l, i-1);
             push2(i+1, r);
           }
           else {
             push2(i+1, r);
             push2(l, i-1);
           }
         }
       }
       
       void partition(Item a[], int l, int r, int *ii, int *jj)
       {
         int i,j, k, p, q;
         Item v;
       
         /* refinement 3: median-of-three(sampling) partitioning */
         exch(a[(l+r)/2], a[r-1]);
         compexch(a[l], a[r-1]);
         compexch(a[l], a[r]);
         /* the median is left at the right end to serve as the pivot */
         compexch(a[r], a[r-1]);
       
         v = a[r];
         i = l-1;
         j = r;
         p = l-1;
         q = r;
       
         for (;;)
         {
           while (less(a[++i], v)) ;   /* a[l] serves as sentinel */
           while (less(v, a[--j])) ;   /* a[r] serves as sentinel */
           if (i >= j) break;
           if (eq(a[i], v)) {
             ++p;
             /* throw equals to the ends */
             exch(a[p], a[i]);
             if (eq(a[j], v)) {
               --q;
               /* throw equals to the ends */
               exch(a[q], a[j]);
             }
             else {
               /* a[j] will be processed in next loop */
               ++j;
             }
           }
           else if (eq(v, a[j])) {
             --q;
             /* throw equals to the ends */
             exch(a[q], a[j]);
             /* a[i] will be processed in next loop */
             --i;
           }
           else {
             exch(a[i], a[j]);
           }
         }
       
         /* crossing at an element equal to v */
         if (i == j) {
           exch(a[i+1], a[r]);
           j = i-1;
           i = i+2;
         }
         else {
           exch(a[i], a[r]);
           j = i-1;
           i = i+1;
         }
         /* refinement 4: three-way partitioning */
         /* move the equals from ends to middle */
         /* move the lesses to the left subfile */
         /* move the largers to the right subfile */
         for (k = l  ; k <= p; ++k, --j) exch(a[k], a[j]);
         for (k = r-1; k >= q; --k, ++i) exch(a[k], a[i]);
         *ii = i;
         *jj = j;
       }
                            

  6. Merge Sort
     • advantages: it has a guaranteed O(NlgN) running time; it is normally implemented such that it accesses the data primarily sequentially, thus it is the method of choice for sorting a linked list, where sequential access is the only kind of access available.
     • disadvantages: extra space proportional to N is needed.
     • stability: stable.
     • operations: NlgN comparisons
     • space: O(N) extra space is needed.
     • implementation in C:

       void mergeAB(Item c[], Item a[], int N, Item b[], int M)
       {
         int i, j, k;
         for (i = 0, j = 0, k = 0; ; ++k) {
           if (i == N) break;
           if (j == M) break;
       /*     c[k] = less(b[i], a[i]) ? b[i++] : a[j++];     */
           /* keep stability in the assumption that a[] is before b[] in the
            * original sequence */
           c[k] = less(b[i], a[i]) ? b[i++] : a[j++];
         }
       
         if (i == N) {
           for ( ; k < M + N; ++k) {
             c[k] = b[j++];
           }
         }
         else {                        /* j == M */
           for ( ; k < M + N; ++k) {
             c[k] = a[i++];
           }
         }
       }
       
       Item aux[maxN];
       
       void merge_sortAB(Item a[], Item b[], int l, int r)
       {
         int m = (l + r) / 2;
         if (r - 1 < 10) {             /* improvement 1: cutoff for small subfiles */
           insertion_sort(a, l, r);
           return;
         }
       
         merge_sortAB(b, a, l, m);
         merge_sortAB(b, a, m + 1, r);
         mergeAB(a + l, b + l, m - l + 1, b + m + 1, r - m);
       }
       
       void merge_sort(Item a[], int l, int r)
       {
         int i;
         /* improvement 2: merge data in a flip-flop manner between two arrays
          * to eliminate the time taken to copy to the auxiliary array in
          * every merging */
         for (i = l; i <= r; ++i) aux[i] = a[j];
         merge_sortAB(a, aux, l, r);
       }
       

  7. Heap Sort
     • advantages: it has a guaranteed O(NlogN) running time sort; it is in-place sort; it is insensitive to input.
     • disadvantages: no good locality for cache mechanisms to take advantage of.
     • stability: unstable.
     • operations: fewer than 2NlogN(bottom-up heap construction) or 3NlogN(top-down heap construction) comparisons and exchanges.
     • space: in-space sort, O(N).
     • implementation in C:

       void heap_sort(Item a[], int l, int r)
       {
         int k, N = r - l + 1;
         Item *pq = a + l - 1;
         for (k = N/2; k >= 1; k--)
           fixDown(pq, k, N);
         while (N > 1) {
           exch(pq[1], pq[N]);
           fixDown(pq, 1, --N);
         }
       }
       
       void fixDown(Item a[], int k, int N)
       {
         int i;
         while (2 * k <= N) {
           i = 2 * k;
           if (i < N && less(a[i], a[i+1])) ++i;
           if (!less(a[k], a[i])) break;
           exch(a[k], a[j]);
           k = i;
         }
       }
       

• Non-comparison Sort
  1. Counting Sort
     • advantages: efficient when the key values are limited in a relatively small range with respect to the size of sequence.
     • disadvantages:
     • stability: stable.
     • operations: the running time is proportional to max{max key value(M), size of sequence(N)}, thus linear when the range of key values is within a constant factor of the sequence size.
     • space: O(N) + O(N) + O(M).
     • implementation in C:

       void counting_sort(int a[], int l, int r)
       {
         int i, j, cnt[M];
         int b[maxN];
         for (j = 0; j < M; ++j) cnt[j] = 0;
         for (i = l; i <= r; ++i) ++cnt[a[i] + 1];
         for (j = 1; j < M; ++j) cnt[j] += cnt[j - 1];
         for (i = l; i <= r; ++i) b[cnt[a[i]]++] = a[i];
         for (i = l; i <= r; ++i) a[i] = b[i];
       }
                          

  2. Radix Sort
     • advantages: it is based on key-indexed counting sort.
     • disadvantages: it does not work well on files that contain huge numbers of duplicate keys that are not short, because all the bits of equal keys are examined.
     • stability: stable.
     • Approaches:
       1. MSD (most-significant-digit) Radix Sort
          • advantages: generalizes quick sort; examines the minimum amount of information necessary to get a sorting job done; is insensitive to key order.
          • disadvantages: is sensitive to the distribution of key values, and does not work well for nonrandom data; produces a large number of small or even empty bins in the late stages.
          • operations: can be sublinear in the total number of data bins, because the whole key does not necessarily have to be examined; O(Nlog_RN) on average; within a small constant factor of the number of bits in the keys in the worst case.
          • space: extra O(N) + O(R) space is required in each pass.
          • Implementation in C:

            #define bin(A) l+count[A]
            #define digit(A, B) ...          /* retrive the Bth digit of A */
            void radixMSD(Item a[], int l, int r, int w)
            {
              int i, j, count[R+1];
              if (w > bytesword) return;
              /* cutoff for small file */
              if (r-l <= M) {
                insertion(a, l, r);
                return;
              }
              for (j = 0; j < R; j++) count[j] = 0;
              for (i = l; i <= r; i++)
                count[digit(a[i], w) + 1]++;
              for (j = 1; j < R; j++)
                count[j] += count[j-1];
              for (i = l; i <= r; i++)
                aux[l+count[digit(a[i], w)]++] = a[i];
              for (i = l; i <= r; i++) a[i] = aux[i];
              radixMSD(a, l, bin(0)-1, w+1);
              for (j = 0; j < R-1; j++)
                radixMSD(a, bin(j), bin(j+1)-1, w+1);
            }
                  

       2. Three-Way Radix Quick Sort (comparison sort)
          • advantages: hybrid of quick sort and MSD radix sort.
            • comparison with MSD: avoids large number of empty bins, adapts well to handle duplicate keys, keys that fall into a small range, small files, different types of nonrandomness; no auxiliary array is required; is independent of the radix.
            • comparison with quick sort: avoid redundant comparisons over all the equal leading bytes which are already compared during the previous stages.
          • disadvantages: three-way partition is slow compared with multiway partition that extra exchanges are required to get the equivalent partitioning effect.
          • operations: 2NlnN byte comparisons on average.
          • space: in-place sort, O(N).
          • Implementation in C:

            #define ch(A) digit(A, D)
            void quicksortX(Item a[], int l, int r, int D)
            {
              int i, j, k, p, q;
              int v;
              if (r-l <= M) {
                insertion(a, l, r);
                return;
              }
              v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
              while (i < j)
              {
                while (ch(a[++i]) < v) ;
                while (v < ch(a[--j])) if (j == l) break;
                if (i > j) break;
                exch(a[i], a[j]);
                if (ch(a[i])==v) { p++; exch(a[p], a[i]); }
                if (v==ch(a[j])) { q--; exch(a[j], a[q]); }
              }
              /* all are equal at digit D */
              if (p == q)
              {
                if (v != END_OF_KEY) quicksortX(a, l, r, D+1);
                return;
              }
              if (ch(a[i]) < v) i++;
              for (k = l; k <= p; k++, j--) exch(a[k], a[j]);
              for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
              quicksortX(a, l, j, D);
              if ((i == r) && (ch(a[i]) == v)) i++;
              if (v != END_OF_KEY) quicksortX(a, j+1, i-1, D+1);
              quicksortX(a, i, r, D);
            }
                  

       3. LSD (least-significant-digit) Radix Sort
          • advantages: it involves extremely simple control structures and its basic operations are suitable for machine-language implementation, which can directly adapt to special-purpose high-performance hardware; it has moderate performance independent of the input.
          • disadvantages: does no work unless the sort method used is stable; is based on fixed-length key; may do unnecessary work on the right parts of the keys; key abstraction operations are not as efficient as general comparison operations in conventional programming environments, so a more costly inner loop than quick sort or merge sort.
          • operations: N(w/lgR) byte comparisons with w-bit keys.
          • space: extra O(N) + O(R) space is required.
          • Implementation in C:

            void radixLSD(Item a[], int l, int r)
            {
              int i, j, w, count[R+1];
              for (w = bytesword-1; w >= 0; w--)
              {
                for (j = 0; j < R; j++) count[j] = 0;
                for (i = l; i <= r; i++)
                  count[digit(a[i], w) + 1]++;
                for (j = 1; j < R; j++)
                  count[j] += count[j-1];
                for (i = l; i <= r; i++)
                  aux[count[digit(a[i], w)]++] = a[i];
                for (i = l; i <= r; i++) a[i] = aux[i];
              }
            }
                  

Definitions:

• Inversion: An inversion is a pair of keys that are out of order in the sequence.
• Left inversion: The number of larger elements to the left of an element.
• Right inversion: The number of smaller elements to the right of an element.