Array Sorting Algorithms

Insertion Sort (n²)

 static void insertionSort(int[] a) {
        for (int i = 2; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j > 0 && a[j] > key) {
                a[j + 1] = a[i];
                j--;
            }
            a[j + 1] = key;
        }
    }

Merge Sort (n lg n)

package vvirlan.sorting;

import vvirlan.utils.PrintUtils;

public class MergeSort {
    public static void main(String[] args) {
        int[] A = new int[]{37, 0, 1, 35, 39, 44, 2, 25, 8, 43, 48, 34, 6, 50, 15, 5, 26, 47, 49, 24};
        mergeSort(A, 0, A.length - 1);
        PrintUtils.print1DArray(A);
    }

    static void mergeSort(int[] A, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);
        }
    }


    static void merge(int[] A, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];

        for (int i = 0; i < n1; i++) {
            L[i] = A[p + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j + 1];
        }
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
        }
    }
}