Java implementation of Mergesort and Quicksort. It's the allocation of the array destination on line 29 in Mergesort.java that creates the memory management complications. In Java we don't have to worry about freeing up that memory because the garbage collector takes care of it for us, but in C we'll have to look after that ourselves.

Mergesort.java

package umm.systems;

public class Mergesort implements Sorter {

  @Override
  public void sort(int[] values) {
    mergesortRange(values, 0, values.length);
  }

  private void mergesortRange(int[] values, int startIndex, int endIndex) {
    int rangeSize = endIndex - startIndex;
    if (needsSorting(rangeSize)) {
      int midPoint = (startIndex + endIndex) / 2;
      mergesortRange(values, startIndex, midPoint);
      mergesortRange(values, midPoint, endIndex);
      mergeRanges(values, startIndex, midPoint, endIndex);
    }
  }

  private void mergeRanges(int[] values, int startIndex, int midPoint,
  int endIndex) {
    /*
     * Assume that the two ranges are sorted:
     *   (forall i | startIndex <= i <= j < midPoint : values[i] <= values[j])
     *   (forall i | midPoint <= i <= j < endIndex : values[i] <= values[j])
     * then merge them into a single sorted array, copy that back, and return.
     */
    final int rangeSize = endIndex - startIndex;
    int[] destination = new int[rangeSize];
    int firstIndex = startIndex;
    int secondIndex = midPoint;
    int copyIndex = 0;
    while (firstIndex < midPoint && secondIndex < endIndex) {
      if (values[firstIndex] < values[secondIndex]) {
        destination[copyIndex] = values[firstIndex];
        ++firstIndex;
      } else {
        destination[copyIndex] = values[secondIndex];
        ++secondIndex;
      }
      ++copyIndex;
    }
    while (firstIndex < midPoint) {
      destination[copyIndex] = values[firstIndex];
      ++copyIndex;
      ++firstIndex;
    }
    while (secondIndex < endIndex) {
      destination[copyIndex] = values[secondIndex];
      ++copyIndex;
      ++secondIndex;
    }
    for (int i = 0; i < rangeSize; ++i) {
      values[i + startIndex] = destination[i];
    }
  }

  private boolean needsSorting(int rangeSize) {
    return rangeSize >= 2;
  }

}

Quicksort.java

package umm.systems;

public class Quicksort implements Sorter {

    private int firstPivotIndex;
    private int afterLastPivotIndex;

    @Override
    public void sort(int[] values) {
        quicksortRange(values, 0, values.length);
    }

    private void quicksortRange(int[] values, int startIndex, int endIndex) {
        int rangeSize = endIndex - startIndex;
        if (needsSorting(rangeSize)) {
            int pivotValue = choosePivotValue(values, startIndex, endIndex);
            splitOnPivot(values, startIndex, endIndex, pivotValue);
            /*
             * After calling pivot Position it should be the case that:
             *    (forall i | startIndex <= i < firstPivotIndex : values[i] < pivotValue)
             *    (forall i | firstPivotIndex <= i < afterLastPivotIndex : values[i] = pivotValue)
             *    (forall i | afterLastPivotIndex <= i < endIndex : pivotValue < values[i])
             * If that's true, then sorting those two segments in place should be enough
             * to finish up the sorting process.
             */
            quicksortRange(values, startIndex, firstPivotIndex);
            quicksortRange(values, afterLastPivotIndex, endIndex);
        }
    }

    private void splitOnPivot(int[] values, int startIndex, int endIndex,
            int pivotValue) {
        /*
         * Invariants:
         *   firstPivotIndex <= k < afterLastPivotIndex
         *   (forall i | startIndex <= i < firstPivotIndex : values[i] < pivotValue)
         *   (forall i | firstPivotIndex <= i < k : values[i] = pivotValue)
         *   (forall i | afterLastPivotIndex <= i < endIndex : pivotValue < values[i])
         */
        firstPivotIndex = startIndex;
        afterLastPivotIndex = endIndex;
        int k = firstPivotIndex;
        while (k < afterLastPivotIndex) {
            if (values[k] < pivotValue) {
                swap(values, firstPivotIndex, k);
                ++firstPivotIndex;
                ++k;
            } else if (values[k] == pivotValue) {
                ++k;
            } else { // values[k] > pivotValue
                --afterLastPivotIndex;
                swap(values, k, afterLastPivotIndex);
            }
        }
    }

    private void swap(int[] values, int firstIndex, int secondIndex) {
        int value = values[firstIndex];
        values[firstIndex] = values[secondIndex];
        values[secondIndex] = value;
    }

    private int choosePivotValue(int[] values, int startIndex, int endIndex) {
        /*
         * Choosing the first value as the pivot leads to the unfortunate
         * O(N^2) behavior if the list is already sorted (or even nearly sorted)
         * before calling quicksortRange.  Choosing a random index avoids
         * that, but I didn't want to clutter this with random number generation,
         * etc.
         */
        return values[startIndex];
    }

    private boolean needsSorting(int rangeSize) {
        return rangeSize >= 2;
    }

}

Sorter.java

package umm.systems;

public interface Sorter {
  void sort(int[] values);
}