Java Program to sort [closed]

Question

I'm trying to implement a code to mergeSort a list. I was told to use getFirst() and addAll() but I don't know how so this is what I came up with:

Also, I can't use a void for mergeSort method - because it gives me an error so I have to return something.

Any suggestions will be very appreciate

Answer 1

Although there is an accepted answer, this code uses getFirst() and addAll() as mentioned in the original post, in what I assume is the intended purpose of this exercise. It uses a bottom up merge sort, which avoids the top down issue having to scan lists to find mid points to split lists.

The basic concept of a bottom up merge sort is two 1 node lists are merged to create a sorted 2 node list, two sorted 2 node lists are merged to create a sorted 4 node list, two sorted 4 node lists are merged to create a sorted 8 node list, and so on, similar to bottom up merge sort for arrays.

A bottom up merge sort uses a small array of lists (java), pointers to nodes (C), or iterators to nodes (C++) to hold the lists. For this example code, I use an array of 32 lists. For each member of array, the member is either null or refers to a list where the number of nodes for the list for array[i] has 2^i nodes: array[0] 1 node, array[1] 2 nodes, array[2] 4 nodes, ..., array[30] 2^30 = 1 billion nodes. The last member will have 2^31 = 2 billion nodes or more if the total number of nodes is >= 2^32 (4 billion) nodes.

Nodes are removed from the front of the source list one at a time and each node from the source list is used to create a list mm with 1 node, then mm is merged into the array, stopping at the first null encountered:

    while(source_list not empty){
        mm = source_list.removeNode(()   // mm = next node from source list
        for(i = 0; i < 32; i++){         // merge mm into array
            if(array[i] != null){
                mm = merge(array[i], mm)
                array[i] = null
            } else {
                break
            }
        }
        if(i == 32)    // if i == 32, there is no array[32], so 
            i = 31     //  use array[31] instead
        array[i] = mm
    }

The pattern looks like this:

mm = next node from source list  // 1 node list
array[0] = mm

mm = next node from source list  // 1 node list
mm = merge(array[0], mm)         // 2 node list
array[0] = null
array[1] = mm

mm = next node from source list  // 1 node list
array[0] = mm

mm = next node from source list  // 1 node list
mm = merge(array[0], mm)         // 2 node list
array[0] = null
mm = merge(array[1], mm)         // 4 node list
array[1] = null
array[2] = mm

Once the last node is merged into the array, all the lists in the array are merged to form a single sorted list:

        mm = empty list
        for(i = 0; i < 32; i++){
            if(all[i] != null){
                mm = merge(all[i], mm);
                all[i] = null;    // (for garbage collection)
            }
        }

Java's native double linked list class doesn't provide a means to move nodes within a list or between lists, so a node has to be deleted when an element is retrieved from the front of a list, and a node has to be created when an element is appended to the back of a list, an extra overhead. In the case of C++ standard double link list class std::list, std::list::splice() can be used to move nodes within a list or between lists, reducing the overhead, such as dst.splice(dst.end(), src, src.begin()), which moves the beginning node (first node) from src to the ending node (last node) of dst.

    public static LinkedList<Integer> merge(LinkedList<Integer> ll,
                                     LinkedList<Integer> rr)
    {
        if(ll.isEmpty())
            return rr;
        if(rr.isEmpty())
            return ll;
        LinkedList<Integer> mm = new LinkedList<>();
        while(true){
            if(ll.getFirst().compareTo(rr.getFirst()) <= 0){
                mm.add(ll.removeFirst());
                if(!ll.isEmpty())
                    continue;
                mm.addAll(rr);
                break;
            } else {
                mm.add(rr.removeFirst());
                if(!rr.isEmpty())
                    continue;
                mm.addAll(ll);
                break;
            }
        }
        return mm;
    }

    public static LinkedList<Integer> mergeSort(LinkedList<Integer> ll)
    {
        if(ll == null || ll.size() < 2)
            return ll;
        int i;
        final int ASZ = 32;                 // create array (of nulls) 
        LinkedList<Integer>[] all= new LinkedList[ASZ];
        // merge nodes into array
        LinkedList<Integer> mm;
        do{
            mm = new LinkedList<>();        // mm = next node
            mm.add(ll.removeFirst());
                                            // merge mm into array
            for(i = 0; (i < ASZ) && (all[i] != null); i++){
                mm = merge(all[i], mm);
                all[i] = null;
            }
            if(i == ASZ)                    // don't go past end of array
                i--;
            all[i] = mm;
        }while(!ll.isEmpty());
        // merge array into single list
        mm = new LinkedList<>();
        for(i = 0; i < ASZ; i++){
            if(all[i] != null){
                mm = merge(all[i], mm);
                all[i] = null;
            }
        }
        return (mm);
    }

---

test code, takes about 3 to 5 seconds to sort 4 million (2^22) nodes.

public static void main(String[] args) {
    final int COUNT = 4*1024*1024; 
    LinkedList<Integer> ll = new LinkedList<>();
    Random r = new Random();
    for(int i = 0; i < COUNT; i++)
        ll.addLast(r.nextInt());
    long bgn, end;
    bgn = System.currentTimeMillis();
    ll = mergeSort(ll);
    end = System.currentTimeMillis();
    System.out.println("milliseconds " + (end-bgn));
    // check sort
    int i;
    i = ll.removeFirst();
    int j = i;
    while(!ll.isEmpty()){
        j = ll.removeFirst();
        if(i > j)
            break;
        i = j;
    }
    if(i == j)
        System.out.println("passed");
    else
        System.out.println("failed");
 }

---

In the merge code, I'm getting faster and more consistent run times using a loop instead of addAll, from 3 to 5 seconds down to 2.8 to 3.2 seconds, but the assignment states to use addAll.

                //  mm.addAll(rr);    // replace with loop is faster
                do
                    mm.add(rr.removeFirst());
                while(!rr.isEmpty());