1#include <stdio.h>
  2#include <stdlib.h>
  3
  4/**
  5 * Prints a visual dump of an array of
  6 * items to stdout out for debugging.
  7 *
  8 * @param items The items to inspect
  9 * @param n The total # of items in the array.
 10 */
 11static void dump(int *items, int n) {
 12  printf("[");
 13  for (int i = 0; i < n; ++i)
 14    printf("%d,", items[i]);
 15  printf("]\n");
 16}
 17
 18/**
 19 * Merges two subsequences of an array.
 20 *
 21 * @params items A pointer to the start of an array of items
 22 * @param min The starting index of the left sub sequence.
 23 * @param mid The starting index of the right sub sequence.
 24 * @param max The ending index of the right sub sequence.
 25 */
 26static void _merge(int *items, int min, int mid, int max) {
 27  int length = (max - min) + 1;
 28  int tmp[length];
 29  int j = min, k = mid;
 30
 31  for (int i = 0; i < length; i++) {
 32    if (j < mid && k <= max)
 33      if (items[j] < items[k])
 34        tmp[i] = items[j++];
 35      else
 36        tmp[i] = items[k++];
 37    else if (j >= mid)
 38      tmp[i] = items[k++];
 39    else
 40      tmp[i] = items[j++];
 41  }
 42
 43  for (int i = 0; i < length; i++)
 44    items[min + i] = tmp[i];
 45}
 46
 47/**
 48 * Performs a recursive merge sort of items in an array.
 49 *
 50 * @param items An array of integers.
 51 * @param min The starting index of a subsequence to sort
 52 * @param max The ending index of a subsequence to sort
 53 */
 54static void _merge_sort(int *items, int min, int max) {
 55  if (min >= max)
 56    return;
 57
 58  int mid = min + (max - min) / 2;
 59  _merge_sort(items, min, mid);
 60  _merge_sort(items, mid + 1, max);
 61  _merge(items, min, mid + 1, max);
 62}
 63
 64/**
 65 * Partitions a sequence into two subsequences.
 66 *
 67 * @param items An array of integers to partition
 68 * @param min The starting index of the sequence to partition
 69 * @param max The ending index of the sequence to partition
 70 * @return Returns the index that can be used as the partition point for the
 71 * sequence.
 72 */
 73static int partition(int *items, int min, int max) {
 74  int pivot = items[max];
 75  int index = min - 1;
 76  int tmp;
 77
 78  for (int j = min; j < max; j++) {
 79    if (items[j] < pivot) {
 80      index++;
 81      tmp = items[index];
 82      items[index] = items[j];
 83      items[j] = tmp;
 84    }
 85  }
 86  tmp = items[index + 1];
 87  items[index + 1] = items[max];
 88  items[max] = tmp;
 89
 90  return index + 1;
 91}
 92
 93/**
 94 * Performs a recursive quick sort on an array of items.
 95 *
 96 * @param items An array of integers
 97 * @param min The starting index of a subsequence to sort
 98 * @param max The ending index of a subsequence to sort
 99 */
100static void _quick_sort(int *items, int min, int max) {
101  if (min >= max)
102    return;
103
104  int index = partition(items, min, max);
105  _quick_sort(items, min, index - 1);
106  _quick_sort(items, index + 1, max);
107}
108
109/**
110 * Performs a merge sort on an array of integers.
111 *
112 * @param items An array of integers
113 * @param length The # of items in the array of integers
114 */
115void merge_sort(int *items, int length) {
116  if (!items || length <= 0)
117    return;
118
119  _merge_sort(items, 0, length - 1);
120}
121
122/**
123 * Performs a quick sort on an array of integers.
124 *
125 * @param items An array of integers
126 * @param length The # of items in the array of integers
127 */
128void quick_sort(int *items, int length) {
129  if (!items || length <= 0)
130    return;
131
132  _quick_sort(items, 0, length - 1);
133}