Mergesort in Java

A simple implementation of Mergesort in Java.
Mergesort algorithm is used in Java SE Collections.sort() method.
Provided implementation has an optimization which prevents already ordered arrays to be merged thus guarantees O(n*log n) time performance.

Mergesort is particularly useful for "online" sorting which means that all amount of data is not known in advance and is becoming available to sorting mechanism chunk-by-chunk.
In this case algorithm can sort each new chunk and then effectively merge it into existing sorted structure. For such cases mergesort is much more effective than quicksort.

One of the "cons" for mergesort is that it uses O(n) auxiliary memory in distinct of quicksort which operates in constant O(1) memory.

It is possible to implement merge sort to be in-place (use constant auxiliary memory) and stay stable, however these algorithms are overcomplicated and their complexity usually is not balanced by their benefit.

public class Mergesort {
 public static int[] sort(int... array) {
  return new Mergesort().sort(array, 0, array.length - 1);  
 }
 
 private int[] sort(int[] array, int start, int end) {
  if (start >= end) {
   return array;   
  }
  int pivot = start + (end - start) / 2 + 1;
//  At this point end may become bigger than start because of integer
//  division. If pivot == start => pivot - 1 < start
  sort(array, start, pivot - 1);
  sort(array, pivot, end);
  merge(array, start, pivot, end);
  return array;
 }

 public int[] merge(int[] array, int start, int pivot, int end) {
  if (start == end) {
//   array of one element is already sorted
   return array;
  }
  
  if (array[pivot - 1] <= array[pivot]) {
//   Handling the case when array is already properly sorted. This optimization
//   guarantees O(n*log n) sorting time 
   return array;
  }
  
  int length = end - start + 1;
  int[] merged = new int[length];
  for (int i = start, j = pivot, storeIndex = 0; i < pivot || j <= end; storeIndex++) {
   if (i == pivot) {
    merged[storeIndex] = array[j++];
   } else if (j > end) {
    merged[storeIndex] = array[i++];
   } else {
    merged[storeIndex] = array[i] <= array[j] ? array[i++] : array[j++];
   }
  }
  System.arraycopy(merged, 0, array, start, length);
  return array;
 }
}

Quicksort in Java

Java implementation of Quicksort

Best case O(n*log n)
Worst case O(n^2) -- the worst case is appeared when the worst pivot is taken for every iteration. In this case Quicksort acts very similar to bubble-sort.

public class Quicksort {
 public static int[] sort(int... array) {
  Quicksort quicksort = new Quicksort();
  return quicksort.sort(array, 0, array.length - 1);
 }

 private int[] sort(int[] array, int start, int end) {
  if (end - start <= 0) {
//   TODO: Consider other sorting for short arrays
   return array;
  }
  int pivotIndex = selectPivotIndex(array, start, end);
  pivotIndex = partition(array, start, end, pivotIndex);
  sort(array, start, pivotIndex - start);
  sort(array, pivotIndex + 1, end);
  return array;
 }

 private int partition(int[] array, int start, int end, int pivotIndex) {
  int pivotValue = array[pivotIndex];
  int storeIndex = start;
  swap(array, pivotIndex, end);
  
  for (int i = start; i < end; i++) {
   if (array[i] < pivotValue) {
    swap(array, i, storeIndex++);
   }
  }
  swap(array, storeIndex, end);
  return storeIndex;
 }

 private void swap(int[] array, int index1, int index2) {
  int temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
 }

 private int selectPivotIndex(int[] array, int start, int end) {
//  TODO: Consider better pivot selection
  return start + (end - start) / 2;
 }
}