Sorting in Java

Sorting Algorithms

import java.io.*;
import java.util.*;


class Solution {
  
  public static void main(String[] args) {
    int[] original = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 
                      101, 79, 94, 90, 97};
    int[] input = null;
    
    System.out.println("original: " + Arrays.toString(original));
    
    input = original.clone();
    System.out.println("bubble sort: " + Arrays.toString(bubbleSort(input)));
    
    input = original.clone();
    System.out.println("insertion sort: " + Arrays.toString(insertionSort(input)));
    
    input = original.clone();
    System.out.println("merge sort: " + Arrays.toString(mergeSort(input, 0, 
                                                        input.length - 1)));
    
    input = original.clone();
    System.out.println("quick sort: " + Arrays.toString(quickSort(input, 0, 
                                                        input.length - 1)));
  }
  
  public static int[] bubbleSort(int[] input){
    int tmp = 0;
    int i = 0;
    int limit = 0;
    
    while(limit < input.length - 1){
      if(input[i] > input[i + 1]){ // swap
        tmp = input[i + 1];
        input[i + 1] = input[i];
        input[i] = tmp;
      }
      i++;
      
      if(i == input.length - 1 - limit){
        i = 0;
        limit++;
      }
    }
    
    return input;
  }
  
  
  
  
  
  
  
  
  public static int[] insertionSort(int[] input){
    int j = 0;
    int tmp = 0;
    for(int i = 1; i < input.length; i++){
      j = i - 1;
      while(j >= 0 && input[j + 1] < input[j]){ // swap
        tmp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = tmp;
        j--;
      }
    }
    return input;
  }
  
  public static int[] mergeSort(int[] input, int min, int max){
    int mid = (max + min) / 2;
    
    if(min < max){
      mergeSort(input, min, mid);
      mergeSort(input, mid + 1, max);
      merge(input, min, mid, max);
    }
    return input;
  }
  
  public static void merge(int[] input, int min, int mid, int max){
    int[] left = new int[mid - min + 2]; // sentinels
    int[] right = new int[max - mid + 1];
    
    // copy array
    for(int i = 0; i < left.length - 1; i++){
      left[i] = input[min + i];
    }
    left[left.length - 1] = Integer.MAX_VALUE;
    
    for(int i = 0; i < right.length - 1; i++){
      right[i] = input[mid + 1 + i];
    }
    right[right.length - 1] = Integer.MAX_VALUE;
    
    // sort
    int i = 0;
    int j = 0;
    
    for(int n = min; n <= max; n++){
      if(left[i] <= right[j]){
        input[n] = left[i];
        i++;
      }else{
        input[n] = right[j];
        j++;
      }
    }
  }
  
  public static int[] quickSort(int[] input, int min, int max){
    int partitionIndex = 0;
    
    if(min < max){
        partitionIndex = partition(input, min, max);
        quickSort(input, min, partitionIndex - 1);
        quickSort(input, partitionIndex + 1, max);
    }
    
    return input;
  }
  
  public static int partition(int[] input, int min, int max){
    int partitionValue = input[max];
    int i = min - 1;
    int tmp = 0;
    
    for(int j = min; j < max; j++){
      if(input[j] <= partitionValue){
        i++;
        tmp = input[j];
        input[j] = input[i];
        input[i] = tmp;
      }
    }
    
    tmp = input[i + 1];
    input[i + 1] = input[max];
    input[max] = tmp;
    
    return i + 1; // new PartitionIndex
  }
}