Is the combination of insertion-sort and mergesort in Java in-place sorting and stable?

Question

Title: Is this combination of Insertion Sort and Merge Sort in-place and stable?

Body:

Hello everyone,

I have this Java code, which is a combination of Insertion Sort and Merge Sort. I'm not sure if this combined algorithm is considered in-place and stable. I'd appreciate it if someone could help clarify this for me.

Here's the code:

package org.example;

import java.util.Arrays;

public class Main {
    private static Comparable[] aux;

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++) {
            for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid+1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        final int INSERTION_SORT_THRESHOLD = 10;
        if (hi <= lo + INSERTION_SORT_THRESHOLD - 1) {
            insertionSort(a, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;

        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void main(String[] args) {
        Integer[] a = {7, 3, 5, 1, 6, 8, 2, 4, 9, 0};
        System.out.println("Before sorting: " + Arrays.toString(a));
        Main.sort(a);
        System.out.println("After sorting: " + Arrays.toString(a));
    }
}

 

Answer 1

Insertion sort is stable because exchanges only occur on adjacent elements, in your code at a[j] and a[j-1]. Merge sort is also stable, so the combined insertion sort and merge sort would be stable.