sorting algorithm

public class  {
  public int[] selectionSort(int[] array) {
    
    // check other conditions - empty array... etc.
    if (array == null || array.length <= 1) {
      return array;
    }
    for (int i = 1; i < array.length; i++) {
      int tmp = array[i];
      for (j = i; j > 0 && tmp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      array[j] = tmp;
    }
    return array;
  }
}

public class SelectionSort {
  public int[] selectionSort(int[] array) {
    
    // check other conditions - empty array... etc.
    if (array == null || array.length <= 1) {
      return array;
    }
    for (int i = 0; i < array.length - 1; i++) {
      int min = i;
      // find the min element in the subarray of (i, array.length - 1)
      for (int j = i; j < array.length; j++) {
        if (array[j] < min) {
          min = j;
        }
      }
      swap(array, i, min);
    }
    return array;
  }

  private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
  }
}

public int[] mergeSort(int[] array) {
  // check null array first.
  if (array == null) {
    return array;
  }
  // allocate helper array to help merge step,
  // so that we guarantee to more than O(n) space is used.
  // The space complexity is O(n) in this case.
  int[] helper = new int[array.length];
  mergeSort(array, helper, 0, array.length - 1);
  return array;
}

private void mergeSort(int[] array, int[] helper, int left, int right) {
  if (left >= right) {
    return;
  }
  int mid = left + (right - left) / 2;
  mergeSort(array, helper, left, mid);
  mergeSort(array, helper, mid + 1, right);
  merge(array, helper, left, mid, right);
}

private void merge(int[] array, int[] helper, int left, int mid, int right) {
  // copy the content to helper array and we will merge from the helper array
  for (int i = left; i <= right; i++) {
    helper[i] = array[i];
  }
  int leftIndex = left;
  int rightIndex = mid + 1;
  while (leftIndex <= mid && rightIndex <= right) {
    if (helper[leftIndex] <= helper[rightIndex]) {
      array[left++] = helper[leftIndex++];
    } else {
      array[left++] = helper[rightIndex++];
    }
  }
  // if we still have some elements at left side, we need to copy them
  while (leftIndex <= mid) {
    array[left++] = helper[leftIndex++];
  }
  // if there are some elements at right side, we do not need to copy them
  // because they are already in their position
}

public int[] quickSort(int[] array) {
  // check null first
  if (array == null) {
    return array;
  }
  quickSort(array, 0, array.length - 1);
  return array;
}

private void quickSort(int[] array, int left, int right) {
  if (left >= right) {
    return;
  }
  // define a pivot and use the pivot to partition the array.
  int pivotIndex = partition(array, left, right);
  // pivot is already at its position, when we do the recursive call on
  // the two partitions, pivot should not be included in ary of them.
  quickSort(array, left, pivotIndex - 1);
  quickSort(array, pivotIndex + 1, right);
}

private int partition(int[] array, int left, int right) {
  int pivotIndex = getPivotIndex(left, right);
  int pivot = array[pivotIndex];
  // swap the pivot element to the rightmost position first.
  swap(array, pivotIndex, right);
  int leftBound = left;
  int rightBound = right;
  while (leftBound <= rightBound) {
    if (array[leftBound] < pivot) {
      leftBound++;
    } else if (array[rightBound] >= pivot) {
      rightBound--;
    } else {
      swap(array, leftBound++, rightBound--);
    }
  }
  // swap back the pivot element.
  swap(array, leftBound, right);
  return leftBound;
}

private void swap(int[] array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

// this is one of the ways defining the pivot,
// pick random element in the range of [left, right].
private int getPivotIndex(int left, int right) {
  Random rand = new Random();
  return left + rand.nextInt(right - left + 1);
}

public int[] rainbowSort(int[] array) {
  if (array == null || array.length <= 1) {
    return array;
  }
  // three bound:
  // 1. the left side of neg is -1 (exclusive of neg).
  // 2. the right side of one is 1 (exclusive of one).
  // 3. the part between neg and zero is 0 (exclusive of zero).
  // 4. between zero and one is to be discovered. (inclusive of both).
  int neg = 0;
  int zero = 0;
  int one = array.length - 1;
  while (zero <= one) {
    if (array[zero] == -1) {
      swap(array, neg++, zero++);
    } else if (array[zero] == 0) {
      zero++;
    } else {
      swap(array, zero, one--);
    }
  }
  return array;
}

private void swap(int[] array, int a, int b) {
  int temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}