// M - Main Array
                int Aindex = 0;
                int Bindex = 0;
                int A[] = new int[(int) (M.length + 1) / 2];
                int B[] = new int[(int) M.length / 2];
                while (!sakartotsAugosi(M)) { // While not sorted Look below for this function.
                    Aindex = 0;
                    Bindex = 0;
                    for (int Mindex = 0; Mindex < M.length; Mindex++) {
                        if ((Mindex + 1) % 2 != 0) {
                            A[Aindex] = M[Mindex];
                            Aindex++;
                        } else {
                            B[Bindex] = M[Mindex];
                            Bindex++;
                        }
                    }


                    Aindex = 0;
                    Bindex = 0;
                    for (int Mindex = 0; Mindex < M.length; Mindex++) {
                        if (Aindex == A.length) {
                            M[Mindex] = B[Bindex];
                            Bindex++;
                        } else if (Bindex == B.length) {
                            M[Mindex] = A[Aindex];
                            Aindex++;
                        } else if (A[Aindex] <= B[Bindex]) {
                            M[Mindex] = A[Aindex];
                            Aindex++;
                        } else if (B[Bindex] <= A[Aindex]) {
                            M[Mindex] = B[Bindex];
                            Bindex++;
                        }
                    }

public boolean sakartotsAugosi(int M[]) {
    for (int i = 1; i < M.length; i++) {
        if (M[i - 1] > M[i]) {
            return false;
        }
    }
    return true;
}