Ensertion Sort

public static int[] insertionSort(int[] input) {
    for (int i = 1; i < input.length; i++) {
        int current = input[i];
        int j = i - 1;
        while (j >= 0 && current < input[j]) {
            input[j + 1] = input[j];
            j--;
        }
        input[j + 1] = current;
    }
    return input;
}

Bubble Sort

public static int[] bubbleSort(int[] input) {
    for (int i = 0; i < input.length; i++) {
        for (int j = 0; j < input.length - i - 1; j++) {
            if (input[j] > input[j + 1]) {
                int temp = input[j];
                input[j] = input[j + 1];
                input[j + 1] = temp;
            }
        }
    }
    return input;
}

Quick Sort

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        int pivotIndex = partition(arr, start, end);
        quickSort(arr, start, pivotIndex);
        quickSort(arr, pivotIndex + 1, end);
    }
}

private static int partition(int[] arr, int start, int end) {
    int pivotValue = arr[end - 1];
    int swapPos = start;
    for (int i = start; i < end - 1; i++) {
        if (arr[i] < pivotValue) {
            int temp = arr[swapPos];
            arr[swapPos] = arr[i];
            arr[i] = temp;
            swapPos++;
        }
    }
    arr[end - 1] = arr[swapPos];
    arr[swapPos] = pivotValue;
    return swapPos;
}

Merge Sort

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right - 1) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int leftSize = mid - left;
    int rightSize = right - mid;
    int[] leftArr = new int[leftSize + 1];
    int[] rightArr = new int[rightSize + 1];

    System.arraycopy(arr, left, leftArr, 0, leftSize);
    System.arraycopy(arr, mid, rightArr, 0, rightSize);
    leftArr[leftSize] = Integer.MAX_VALUE;
    rightArr[rightSize] = Integer.MAX_VALUE;

    int i = 0, j = 0;
    for (int k = left; k < right; k++) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
    }
}

Selection Sort

public void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Heap Sort

public class MaxHeap {
    private int getParent(int index) {
        return (index - 1) / 2;
    }

    private int getLeft(int index) {
        return 2 * index + 1;
    }

    private int getRight(int index) {
        return 2 * index + 2;
    }

    private void heapify(int[] arr, int size, int root) {
        int largest = root;
        int left = getLeft(root);
        int right = getRight(root);

        if (left < size && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < size && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != root) {
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;
            heapify(arr, size, largest);
        }
    }

    public void buildHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
    }

    public void heapSort(int[] arr) {
        buildHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
}

Stability in Sorting

A sorting algorithm is consdiered stable if two elemnets with equal keys appear in the same order in the sorted output as they appear in the input array. For example, if A[i] == A[j] and i < j before sorting, then i should still precede j after the sort completes.