public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

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

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int curNum = arr[i];
        int curIndex = i - 1;
        while (curIndex >= 0 && arr[curIndex] > curNum) {
            arr[curIndex + 1] = arr[curIndex];
            curIndex--;
        }
        arr[curIndex + 1] = curNum;
    }
}

private void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int left = start;
    int right = end;
    int cur = arr[start];

    while (left < right) {
        while (cur <= arr[right] && left < right) {
            right--;
        }
        while (cur >= arr[left] && left < right) {
            left++;
        }
        swap(arr, left, right);

    }
    swap(arr, start, left);
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
}

public void mergeSort(int[] arr, int start, int end) {
    int[] result = new int[arr.length];

    if (start >= end) {
        return;
    }

    int mid = start + (end - start) / 2;
    int start1 = start;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = end;
    mergeSort(arr, start1, end1);
    mergeSort(arr, start2, end2);

    int k = start;
    while (start1 <= end1 && start2 <= end2) {
        result[k++] = arr[start1] < arr[start2] ? 
            arr[start1++] : arr[start2++];
    }
    while (start1 <= end1) {
        result[k++] = arr[start1++];
    }
    while (start2 <= end2) {
        result[k++] = arr[start2++];
    }
    for (int i = start; i <= end; i++)
        arr[i] = result[i];
}

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