2
\$\begingroup\$

We were asked to improve the merge sort algorithm by introducing insertion sort to the code. We have been tasked with doing this by utilising a "levels" logic. Here is the exact description of the mentioned task:

This parameter will be incremented by 1 inside the merge_sort before the two recursive calls. It will keep track of the level index of the recursion tree. You can set this parameter to 1 before calling merge_sort. Based on this, the index for the first level of the recursion tree becomes 1.

The usual method of merge sort + insertion sort suggested does not use "levels"

(Provided by Bernhard Barker under a similar question as an answer.)

static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
    if (ub - lb <= THRESHOLD)
        insertionSort(f, lb, ub);
    else
    {
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

The improved merge sort method I have come up with is this:

public static void merge_sort_improved(int [] A, int p, int r, int level, int max_level)
{
    int q = (int) Math.floor((p + r) / 2);       
    if (p < r)
    {
        if (level >= max_level)
            insertion_sort_2(A, p, r);      
        else
        {
            level++;
            merge_sort_improved(A, p, q, level, max_level);
            merge_sort_improved(A, q + 1, r, level, max_level);
        }
        merge(A, p, q, r);
        level--;
    }
}

However, I have observed during testing that this method takes longer than the implementation above in some cases but is faster in others.

The whole code:

// import java.util.Arrays;
import java.util.Random;

public class ImprovedMergeSort {

    public static void main(String[] args) {
        int array_size = 65536;
        // int array_size = 16;
        int[] array = new int[array_size];
        int[] array_2 = new int[array_size];
        int[] array_3 = new int[array_size];

        long start_time, end_time, elapsed_time, min_elapsed_time;
        int best_max_level = 1;

        Random rand = new Random();
        rand.setSeed(System.currentTimeMillis());

        for (int i = 0; i < array_size; i++) {
            array[i] = rand.nextInt(100);
            array_2[i] = array[i];
            array_3[i] = array[i];
        }

        // Running time of merge sort
        start_time = System.nanoTime();
        merge_sort(array, 0, array_size - 1);
        end_time = System.nanoTime();
        
        elapsed_time = end_time - start_time;
        
        System.out.printf("Elapsed time in nanoseconds for original merge sort: %d\n", elapsed_time);

        // part (d)
        // Running time of improved merge sort
        start_time = System.nanoTime();
        merge_sort_improved(array_2, 0, array_size - 1, 1, 13);
        end_time = System.nanoTime();
        
        elapsed_time = end_time - start_time;
        
        System.out.printf("Elapsed time in nanoseconds for improved merge sort with max_level=13: %d\n", elapsed_time);
        
//      start_time = System.nanoTime();
//      merge_sort_improved_2(array_2, 0, array_size - 1, 13);
//      end_time = System.nanoTime();
//      
//      elapsed_time = end_time - start_time;
//      
//      System.out.printf("Elapsed time in nanoseconds for improved merge sort with max_level=13: %d\n", elapsed_time);

        // part (e)
        min_elapsed_time = 0;
        
        for (int max_level = 1; max_level <= 17; max_level++) {
            // copy the original array back to input array
            for (int i = 0; i < array_size; i++)
                array[i] = array_3[i];

            // compute running time of merge sort improved here
            start_time = System.nanoTime();
            merge_sort_improved(array, 0, array_size - 1, 1, max_level);
            end_time = System.nanoTime();
            
            elapsed_time = end_time - start_time;
            
            if ((max_level == 1) || (elapsed_time < min_elapsed_time)) {
                min_elapsed_time = elapsed_time;
                best_max_level = max_level;
            }

            System.out.printf("Max level: %d, Elapsed time in nanoseconds: %d\n", max_level, elapsed_time);

        }

        System.out.printf("Best max level: %d, Min elapsed time in nanoseconds: %d\n", best_max_level,
                min_elapsed_time);

    }

    // parts (b)-(d) implement improved merge sort here
    public static void merge_sort_improved(int [] A, int p, int r, int level, int max_level)
    {
        int q = (int) Math.floor((p + r) / 2);
                
        if (p < r)
        {
            if (level >= max_level) {
                insertion_sort_2(A, p, r);
            }
                
            else
            {
                level++;
                // q = (int) Math.floor((p + r) / 2);
                merge_sort_improved(A, p, q, level, max_level);
                merge_sort_improved(A, q + 1, r, level, max_level);
            }
            
            merge(A, p, q, r);
            level--;
        }
    }
    
    public static void merge_sort_improved_2(int[] A,int p, int r, int threshold){
        if (r - p <= threshold)
            insertion_sort_2(A, p, r);
    
        else
        {
            int q = (p + r) / 2;
            merge_sort(A, p, q);
            merge_sort(A, q, r);
            merge(A, p, q, r);
        }
    }

    // indices p and r can start from 0
    public static void merge_sort(int[] A, int p, int r) {
        int q;

        if (p < r) {
            q = (int) Math.floor((p + r) / 2);
            merge_sort(A, p, q);
            merge_sort(A, q + 1, r);
            merge(A, p, q, r);
        }
    }

    public static void merge(int[] A, int p, int q, int r) {
        int n1, n2;
        int i, j;

        n1 = q - p + 1;
        n2 = r - q;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (i = 0; i < n1; i++)
            L[i] = A[p + i];

        for (i = 0; i < n2; i++)
            R[i] = A[q + i + 1];

        i = 0;
        j = 0;

        for (int k = p; k <= r; k++) {
            if (i >= n1) // the left array finished, copy from right array
            {
                A[k] = R[j];
                j++;
                continue;
            }

            if (j >= n2) // the right array finished, copy from left array
            {
                A[k] = L[i];
                i++;
                continue;
            }

            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
        }
    }

    // insertion sort algorithm
    public static void insertion_sort_2(int[] A, int start_index, int end_index) {
        int key;
        int i;

        for (int j = start_index + 1; j < end_index; j++) {
            key = A[j];

            // insert A[j] into the sorted sequence A[starting_index..j-1]
            i = j - 1;

            while ((i >= 0) && (A[i] > key)) {
                A[i + 1] = A[i];
                i = i - 1;
            }

            A[i + 1] = key;
        }
    }

    // insertion sort algorithm
    public static void insertion_sort(int[] A) {
        int key;
        int i;

        for (int j = 1; j < A.length; j++) {
            key = A[j];

            // insert A[j] into the sorted sequence A[1..j-1]
            i = j - 1;

            while ((i >= 0) && (A[i] > key)) {
                A[i + 1] = A[i];
                i = i - 1;
            }

            A[i + 1] = key;
        }
    }

    // prints the elements of the array A on the screen
    public static void print_array(int[] A) {
        System.out.printf("[");
        for (int i = 0; i < A.length - 1; i++) {
            System.out.printf("%d, ", A[i]);
        }

        System.out.printf("%d]\n", A[A.length - 1]);

    }

}

As I expected, it is faster than the "default" merge sort algorithm, and these are the results:

Elapsed time in nanoseconds for original merge sort: 9551833
Elapsed time in nanoseconds for improved merge sort with max_level=13: 8766042
Max level: 1, Elapsed time in nanoseconds: 868102916
Max level: 2, Elapsed time in nanoseconds: 127934125
Max level: 3, Elapsed time in nanoseconds: 100636084
Max level: 4, Elapsed time in nanoseconds: 53176500
Max level: 5, Elapsed time in nanoseconds: 40008875
Max level: 6, Elapsed time in nanoseconds: 30925333
Max level: 7, Elapsed time in nanoseconds: 18650458
Max level: 8, Elapsed time in nanoseconds: 18098958
Max level: 9, Elapsed time in nanoseconds: 7862125
Max level: 10, Elapsed time in nanoseconds: 6666667
Max level: 11, Elapsed time in nanoseconds: 3863416
Max level: 12, Elapsed time in nanoseconds: 3646500
Max level: 13, Elapsed time in nanoseconds: 2776000
Max level: 14, Elapsed time in nanoseconds: 3010667
Max level: 15, Elapsed time in nanoseconds: 3280834
Max level: 16, Elapsed time in nanoseconds: 4677084
Max level: 17, Elapsed time in nanoseconds: 5324667
Best max level: 13, Min elapsed time in nanoseconds: 2776000

I'm trying to understand the logic and workings of this method and wonder if I was successful at it, so any help would be greatly appreciated.

\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

This question is marginally on-topic since you do not understand the behavior of the code that you wrote and maintain. The code is "correct" in the sense of producing ordered entries, but not in the larger sense of satisfying the "always outperform mergesort!" design goal.

Rejecting the helpful labels of

  • lower bound
  • middle
  • upper bound

in favor of the cryptic p, q, r did not improve readability.

Your cited reference offers this argument:

Although merge sort is O(n log n) and insertion sort is O(n²), insertion sort has better constants and is thus faster on very small arrays.

Your code, oddly, relies on a level comparison rather than the cited ub - lb <= THRESHOLD comparison, and we don't see any formulas to relate level to such a threshold.

Listen to what the argument is trying to tell you. We need to measure the C1 and C2 constants. Then we will know when C1 × (N log N) is less than C2 × N², and can sensibly prefer merge- over insertion- sort in that case.

You kind of did that by trying many max_level values. But it happened indirectly. The quantity we really care about is n, which is r - p. Optimal max_level was 13 for this example input array, but it would vary as we offered smaller or larger inputs.

Why does insertion sort win when N is small? Less function call overhead.

\$\endgroup\$
1
  • \$\begingroup\$ The 17 different values are tried because it has been asked to be that way. All the intermediate values written were provided in the assignment from 1 to 17. The level comparison is a requirement as well. Every size and number detail you see here is predetermined by the assignment. I need help with the "level" logic as I'm not sure how it should be exactly. It is true that I don't fully understand this specific example so any help is very much appreciated. \$\endgroup\$
    – Preatorius
    Commented Oct 24, 2023 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.