Merge sort

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(arr, temp, left, mid);
        mergeSort(arr, temp, mid + 1, right);

        if (arr[mid] <= arr[mid + 1]) {
            return;
        }
        merge(arr, temp, left, mid, right);
    }

    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }

        while (i <= mid) {
            arr[k++] = temp[i++];
        }

        while (j <= right) {
            arr[k++] = temp[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 3, 9, 1, 6, 2, 8, 5, 4};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

def merge(arr, temp, left, mid, right):
    for i in range(left, right + 1):
        temp[i] = arr[i]

    i = left
    j = mid + 1
    k = left

    while i <= mid and j <= right:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            k += 1
            i += 1
        else:
            arr[k] = temp[j]
            k += 1
            j += 1

    while i <= mid:
        arr[k] = temp[i]
        k += 1
        i += 1

    while j <= right:
        arr[k] = temp[j]
        k += 1
        j += 1


def merge_sort_helper(arr, temp, left, right):
    if left >= right:
        return

    mid = left + (right - left) // 2
    merge_sort_helper(arr, temp, left, mid)
    merge_sort_helper(arr, temp, mid + 1, right)

    if arr[mid] <= arr[mid + 1]:
        return
    merge(arr, temp, left, mid, right)


def merge_sort(arr):
    temp = [0] * len(arr)
    merge_sort_helper(arr, temp, 0, len(arr) - 1)


if __name__ == "__main__":
    arr = [7, 3, 9, 1, 6, 2, 8, 5, 4]
    merge_sort(arr)
    print(arr)

Type	Value
Time	O(n log n)
Space	O(n)

Quick Sort

import java.util.Arrays;

public class QuickSort {
    public static int partition(int[] arr, int low, int high) {
        int i = low;
        int j = high;
        int pivot = arr[low];

        while (i < j) {
            while (i <= high && arr[i] <= pivot) {
                i++;
            }
            while (j >= low && arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        swap(arr, low, j);
        return j;
    }

    public static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 5, 100, -12};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

def swap(arr, l, r):
    temp = arr[l]
    arr[l] = arr[r]
    arr[r] = temp


def partition(arr, low, high):
    i = low
    j = high
    pivot = arr[low]

    while i < j:
        while i <= high and arr[i] <= pivot:
            i += 1
        while j >= low and arr[j] > pivot:
            j -= 1
        if i < j:
            swap(arr, i, j)
    swap(arr, low, j)
    return j


def quick_sort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)


if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90, 5, 100, -12]
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)

Type	Value
Time	O(n log n)
Space	O(log n)