public int[] merge(int[] leftSortedArray, int[] rightSortedArray) {
        if (leftSortedArray == null)
            return rightSortedArray;
        else if (rightSortedArray == null)
            return leftSortedArray;
        int p = 0;
        int q = 0;
        int r = 0;
        int combinedSize = leftSortedArray.length + rightSortedArray.length;
        int[] sortedArray = new int[combinedSize];
        while (r < combinedSize && p < leftSortedArray.length && q < rightSortedArray.length) {
            if (leftSortedArray[p] <= rightSortedArray[q]) {
                sortedArray[r] = leftSortedArray[p];
                p++;
            } else {
                sortedArray[r] = rightSortedArray[q];
                q++;
            }
            r++;
        }

        // copy back the remaining elements of left array
        while (p < leftSortedArray.length) {
            sortedArray[r] = leftSortedArray[p];
            p++;
            r++;
        }

        // copy back remaining elements of right array
        while (q < rightSortedArray.length) {
            sortedArray[r] = rightSortedArray[q];
            q++;
            r++;
        }

        return sortedArray;
    }