MergeSort Using a Non-Recursive Sort Threshold

Question

Problem

Create a program to perform a merge sort on a linked list.

Specification

• Create a linked list of 100 random integers in the range 1-1000.
• Display the unsorted linked list in a 10 x 10 table.

To sort the linked list using a merge sort routine:

• Convert the linked list to an array.
• Perform a recursive merge sort on the array.
• Change the merge sort algorithm to use a non-recursive algorithm (selection sort, insertion sort) when the size of the partitions is below some threshold.
• Insert a comment in the merge sort routine that explainsyour reasons for choosing either selection sort, insertion sort, or some other non-recursive algorithm, and how you decided (empirical evidence) what the threshold would be.
• Once the sort is complete, convert the array back into a linked list.
• Display the sorted linked list in a 10 x 10 table.

My code so far:

public class MergeSort{
    LinkedQueue<Integer> list = new LinkedQueue<Integer>();
    Integer[] a = new Integer[100];

    public MergeSort() {
        for(int i=0; i<100; i++)
        {
            list.enqueue(StdRandom.uniform(999)+1);
        }
    }

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

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
    {
        for(int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo, j= mid+1;
        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, Comparable[] aux, int lo, int hi)
    {
        if((hi-lo) <= 6)
        {
            Comparable[] b = new Comparable[hi-lo];
            for(int i=0; i<b.length; i++)
            {
                b[i] = a[lo+i];
            }
            Selection.sort(b);

            for(int i=0; i<(hi-lo); i++)
            {
                a[lo+i] = b[i];
            }
            return;
        }
        int mid = lo + (hi - lo)/2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid+1, hi);
        merge(a, aux, lo, mid, hi);
    }

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

    public static void main(String[] args)
    {
        MergeSort merge = new MergeSort();

        StdOut.println("Unsorted: ");
        for(int i=0; i<10; i++)
        {
            for(int j=0; j<10; j++)
            {
                StdOut.print(merge.list.peek() + " ");
                merge.a[i*10 + j] = merge.list.dequeue();
            }
            StdOut.println();
        }
        StdOut.println();

        merge.sort(merge.a);
        for(int i=0; i<100; i++)
        {
            merge.list.enqueue(merge.a[i]);
        }
        StdOut.println("Sorted: ");
        for(int i=0; i<10; i++)
        {
            for(int j=0; j<10; j++)
            {
                StdOut.print(merge.list.dequeue() + " ");
            }
            StdOut.println();
        }
    }

}   

My problem is that the array only seems to get partially sorted. The first half is sorted fine, but somewhere around the second half, it begins to only have every other item sorted, while the others seem random. Here's an example of an output:

Unsorted: 
580 314 331 643 597 587 798 980 87 53 
526 787 993 336 552 338 950 460 441 566 
428 115 670 28 384 596 781 489 630 91 
272 563 428 644 696 120 538 729 477 637 
196 564 784 770 702 56 992 413 753 266 
847 751 659 426 59 738 185 589 650 636 
849 437 361 519 980 723 973 217 414 548 
337 935 656 944 485 233 431 170 327 832 
53 236 447 184 842 286 303 153 697 713 
303 64 268 725 229 127 517 15 427 372 

Sorted: 
15 28 53 53 56 59 64 87 91 115 
120 127 170 184 196 217 229 233 268 272 
286 303 303 314 327 331 336 337 338 413 
426 427 428 428 431 437 447 460 477 489 
517 372 519 526 538 548 552 564 566 580 
587 589 596 597 630 636 637 643 644 650 
656 659 670 384 696 697 702 713 723 725 
729 738 751 753 781 563 784 770 787 798 
832 236 842 153 847 185 849 361 935 944 
485 950 441 973 980 980 414 992 266 993 

I believe I have narrowed the issue down to the base case of the recursive sort method:

    if((hi-lo) <= 6)
        {
            Comparable[] b = new Comparable[hi-lo];
            for(int i=0; i<b.length; i++)
            {
                b[i] = a[lo+i];
            }
            Selection.sort(b);

            for(int i=0; i<(hi-lo); i++)
            {
                a[lo+i] = b[i];
            }
            return;
        }

Whenever I replace this with the if(hi <= lo) return; base case that is standard with the basic merge sort, everything works fine. So, can anyone help me with this issue, or find an error in the code? Also, if you could give me any suggestions on the issue of why I should use another non-recursive sorting method over Selection, that would be most appreciated.

Source code for Selection class, as requested by Kraskevich:

import java.util.Comparator;

/**
 *  The <tt>Selection</tt> class provides static methods for sorting an
 *  array using selection sort.
 *  <p>
 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Selection {

    // This class should not be instantiated.
    private Selection() { }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
    }

    /**
     * Rearranges the array in ascending order, using a comparator.
     * @param a the array
     * @param c the comparator specifying the order
     */
    public static void sort(Object[] a, Comparator c) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(c, a[j], a[min])) min = j;
            }
            exch(a, i, min);
            assert isSorted(a, c, 0, i);
        }
        assert isSorted(a, c);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/

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

    // is v < w ?
    private static boolean less(Comparator c, Object v, Object w) {
        return (c.compare(v, w) < 0);
    }


    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/

    // is the array a[] sorted?
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // is the array a[] sorted?
    private static boolean isSorted(Object[] a, Comparator c) {
        return isSorted(a, c, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(c, a[i], a[i-1])) return false;
        return true;
    }



    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; selection sorts them; 
     * and prints them to standard output in ascending order. 
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Selection.sort(a);
        show(a);
    }
}

Answer 1

The error is rather simple: lo and hi indices are inclusive. That's why it should be:

if (hi - lo) <= 6) {
    Comparable[] b = new Comparable[hi - lo + 1];
    //                                       ^^^^
    //                                We need plus one here.
    for (int i = 0; i < b.length; i++) {
        b[i] = a[lo + i];
    }
    Selection.sort(b);
    for (int i = 0; i < b.length; i++) {
        //               ^^^^
        //    We should either iterate to hi - lo + 1 or b.length.
        a[lo + i] = b[i];
    }
    return;
}