is there a difference in time/space complexity between recursive and non-recursive merge sort algorithm?

Question

I have implemented a merge sort algorithm using divide and conquer approach where an array is split into two sub arrays.

In my code i re-used insertion sort algorithm to sort the sub arrays in merge sort. Is this right approach or i have to use different sorting approach to sort the sub arrays in merge sort ?

As far as concerned with the understanding of merge sort algorithm, everything is clear but when coming to the implementation of merge sort, how does it happen to divide an array into n-sub arrays without using recursive strategy.

is recursive or non-recursive efficient way to implement merge sort ?

Below is my code snippet in github: https://github.com/vamsikankipati/algorithms-in-java/blob/master/src/com/algorithms/sort/MergeSort.java

I have understood from implementation perspective that my code is wrong as i divided the array into only two sub arrays instead of n-sub arrays.

Any help needed to clearly understand merge sort in terms of algorithm implementation perspective.

Here is the code:

package com.algorithms.sort;

public class MergeSort {

    public static int[] increasing(int[] arr) {
        int[] result = new int[arr.length];
        int q = arr.length / 2;
        System.out.println("q: " + q);
        int[] left = new int[q];
        int[] right = new int[q];
        for (int i = 0; i < q; i++) {
            left[i] = arr[i];
        }
        int k = 0;
        for (int j = q; j < arr.length; j++) {
            right[k] = arr[j];
            k += 1;
        }
        left = InsertionSort.increasing(left);
        right = InsertionSort.increasing(right);

        // Printing
        for (int e : left) {
            System.out.print(e);
        }
        System.out.println("\n");
        for (int e : right) {
            System.out.print(e);
        }
        System.out.println("\n");

        int i = 0;
        int j = 0;
        int s = 0;
        while ((i < left.length) && (j < right.length)) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < left.length) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < right.length) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 1

More important than optimisation, you must first achieve correctness. There is a bug in the increasing static method: if the size of the array argument is not even, the right subarray is allocated with an incorrect size: int[] right = new int[q]; should be

int[] right = new int[arr.length - q];

Furthermore, you should not try to split the array if it is too small.

Regarding optimisation, you should only fallback to InsertionSort() when the subarray size is below a threshold, somewhere between 16 and 128 elements. Careful benchmarking with different thresholds and a variety of distributions will help determine a good threshold for your system.

As currently implemented, your function has a time complexity of O(N²) because it defers to InsertionSort for all but the last merge phase. To reduce the complexity to O(N.log(N)), you must recurse on the subarrays until their size is below a fixed threshold.

Here is a modified version:

package com.algorithms.sort;

public class MergeSort {

    public static int threshold = 32;

    public static int[] increasing(int[] arr) {
        if (arr.length <= threshold)
            return InsertionSort.increasing(arr);

        int len1 = arr.length / 2;
        int[] left = new int[len1];
        for (int i = 0; i < len1; i++) {
            left[i] = arr[i];
        }
        int len2 = arr.length - len1;
        int[] right = new int[len2];
        for (int i = 0; i < len2; i++) {
            right[i] = arr[i + len1];
        }
        left = increasing(left);
        right = increasing(right);

        int[] result = new int[len1 + len2];
        int i = 0;
        int j = 0;
        int s = 0;
        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < len1) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < len2) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 2

Both time complexity is O( n log n).

About space complexity, the implementation may vary on your data structure choice. in recursive if you choose array: space complexity: N log N if you choose linked-list: space complexity is O(1) in iterative: if you choose array: space complexity: N ( based on your implementation it is O ( N log N) because you create a new sub-array in every dividing state, to reduce it to O(n) you should use one extra array as size of the original one, and indexes) if you choose linked-list: space complexity is O(1)

As you can see linked-list is best for sorting. Beyond that recursive may consume more memory than expected based on programming language because of function frame creation.

Source