Friday, March 29, 2013

Merge Sort

Merge Sort

Merge Sort

Introduction

Merge sort works based on the fact that it is relatively easy to take 2 sorted lists and merge them into a larger sorted list. Once we have a merge operation the rest of the sorting routine is relatively simple. Merge sort is also a faster sorting algorithm than either selection sort or insertion sort (on moderate sized lists or arrays anyway). It has to do with the divide and conquer structure of the recursive solution. Merge sort's one draw back is that it is memory intensive. At each level of recursion a new list has to be created to hold the merged smaller lists until the program get's back to the top level call where a new list of sorted elements is provided. In the other 2 sorts the sorting is done inline and only a 'tmp' variable is needed to swap the values when necessary. Memory used to be a big thing now adays not so much. Memory for computers is relatively cheap and many gigabytes may be had for a few hundred dollars.

Merge operation

I will develop the merge sort in the same SortLab class as the other sort routines. First step in the merge sort is let's develop the merge operation.

Specifications

  • Take two int[] parameters that are assumed to be sorted
  • return a new int[] whose length is the size of list1.length + list2.length
  • The returned int[] should have its elements sorted in ascending order

Even though the lists are sorted this operation needs to track a few things:

  • One array may run out of elements early at which point just add in the last elements from the other array
  • Even if they alternate they may not alternate evenly so we must track where we are in each contributing array
  • In the first round of testing merge will be a static routine. Once we go to a full merge sort we will instantiate an object as we did for the other routines

merge code

public static int[] merge(int[] a, int[] b)
{
    int[] m = new int[a.length + b.length];
    int i=0;
    int j=0;

    for (int k = 0; k < m.length; k++)
    {
        if (i < a.length && j < b.length) {
        if (a[i]<=b[j]) {
            m[k] = a[i];
            i++;
        }
        else {
            m[k] = b[j];
            j++;
        }
        }
        else if (i < a.length) {  // b exhausted use up a
            m[k] = a[i];
            i++;
        }
        else { // b still has some left use up those
            m[k] = b[j];
            j++;
        }
    }
    return m;
}

public static void main(String[] args) {
    SortLab select = new SortLab();
    SortLab selectA = new SortLab();
    SortLab insert = new SortLab();
    SortLab insertA = new SortLab();

    System.out.println("Selection Sort");
    System.out.print("unsorted: ");
    select.display();
    select.selection();
    System.out.print("sorted:   ");
    select.display();
    System.out.println("SelectionA Sort");
    System.out.print("unsorted: ");
    selectA.display();
    selectA.selectionA();
    System.out.print("sorted:   ");
    selectA.display();
    System.out.println();
    System.out.println();
    System.out.println("Insertion Sort");
    System.out.print("unsorted: ");
    insert.display();
    insert.insertion();
    System.out.print("sorted:   ");
    insert.display();
    System.out.println("Insertion Sort with Explicit Shift");
    System.out.print("unsorted: ");
    insertA.display();
    insertA.insertion();
    System.out.print("sorted:   ");
    insertA.display();

    System.out.println("Merge Testing");
    int[] l1 = {0, 2, 3, 4, 6, 7, 9};
    int[] l2 = {1, 3, 5, 8, 10};
    int[] l3 = merge(l1,l2);
    for (int i : l3)
    {
        System.out.print(i + " ");
    }
    System.out.println();
}

Output 1

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Merge Testing
0 1 2 3 3 4 5 6 7 8 9 10

Splitting the list

Splitting is the next thing to tackle, the straight forward way would be to just add the beginning index and the ending index together and divide by 2. This cuts the list in half. If we start with a list with 10 things in it, the starting index = 0 and the ending index = 9. (0+9)/2 = 4 we split the list after four (4). This gives us 2 lists from 0 - 4 and 5 - 9. We then want to split the list again and again until ideally all we are left with is 10 single element list. If you work this out on various size arrays you end up needing to help a little when you get to a pair of indexes. So my implementation will treat single indexes and pair indexes as the test case for recursion.

Given the above for background lets look at some pseudo code. I will assume that the original list is the labArray field and mergesort will track indexes into that array. 

public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
    return newArray;
  }
  int split = (begin + end)/2;
  return merge(mergesort(begin, split), mergesort(split+1,end));
}

This works rather nicely. I have made some changes to the actual code over the above pseudo code to display interim results during the merge sort. The full code includes all the sorting routines we have done so far and the work on merge. Finally the code for the mergesort routine itself. It's implemented as a recursive routine as shown in the pseudocode.

The new routines I've added a new display(int[] array) method to display the new arrays that get built during the mergesort. I have also changed all 'for' statements to the for-each version where possible so you can compare it's use to a standard for loop in the previous implementation. I also use the 'display' methods where I can.

Final Code

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i : this.labArray) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void display(int[] array) {
        for( int i : array)
        {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertionShift()
    {
        int j;
        int tmp;

        for (int i = 1; i < this.len; i++) {
            // take ith element find where it should be inserted
            tmp = this.labArray[i];
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                // no need to do anything
                // when the loop ends j will be the insertion position
            }
            // Shift elements from j to i-1 over 1
            for (int k = i - 1; k >= j; k--)
            {
                this.labArray[k + 1] = this.labArray[k];
            }
            this.labArray[j] = tmp;
            System.out.print("interim:  ");
            this.display();
        }
    }

    public int[] merge(int[] a, int[] b)
    {
        int[] m = new int[a.length + b.length];
        int i=0;
        int j=0;

        for (int k = 0; k < m.length; k++)
        {
            if (i < a.length && j < b.length) {
            if (a[i]<=b[j]) {
                m[k] = a[i];
                i++;
            }
            else {
                m[k] = b[j];
                j++;
            }
            }
            else if (i < a.length) {  // b exhausted use up a
                m[k] = a[i];
                i++;
            }
            else { // b still has some left use up those
                m[k] = b[j];
                j++;
            }
        }
        return m;
    }

    public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  int split = (begin + end)/2;
  newArray = this.merge(this.mergesort(begin, split), this.mergesort(split+1,end));
  System.out.print("interim:  ");
  this.display(newArray);
  return newArray;
}


    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();
        SortLab insertA = new SortLab();
        SortLab msort = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
        System.out.println("Insertion Sort with Explicit Shift");
        System.out.print("unsorted: ");
        insertA.display();
        insertA.insertion();
        System.out.print("sorted:   ");
        insertA.display();
        System.out.println("\n");
        System.out.println("Merge Testing");
        int[] l1 = {0, 2, 3, 4, 6, 7, 9};
        int[] l2 = {1, 3, 5, 8, 10};
        int[] l3 = msort.merge(l1,l2);
        System.out.print("l1 = ");
        msort.display(l1);
        System.out.print("l2 = ");
        msort.display(l2);
        System.out.print("l3 = merge(l1,l2) = ");
        msort.display(l3);
        System.out.println("\n");

        System.out.println("merge sort");
        System.out.print("unsorted: ");
        msort.display();
        int[] sorted  = msort.mergesort(0,msort.len-1);
        System.out.print("sorted:   ");
        msort.display(sorted);
    }
}

Output 2

run:
Selection Sort
unsorted: 6  2  5  0  3  8  7  1  4  9  
interim:  0  2  5  6  3  8  7  1  4  9  
interim:  0  1  5  6  3  8  7  2  4  9  
interim:  0  1  2  6  3  8  7  5  4  9  
interim:  0  1  2  3  6  8  7  5  4  9  
interim:  0  1  2  3  4  8  7  5  6  9  
interim:  0  1  2  3  4  5  7  8  6  9  
interim:  0  1  2  3  4  5  6  8  7  9  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 0  3  1  6  9  5  8  4  2  7  
interim:  0  3  1  6  9  5  8  4  2  7  
interim:  0  1  3  6  9  5  8  4  2  7  
interim:  0  1  2  6  9  5  8  4  3  7  
interim:  0  1  2  3  9  5  8  4  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  6  9  8  7  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 1  3  2  7  6  0  9  8  5  4  
interim:  1  3  2  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  6  7  0  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  8  9  5  4  
interim:  0  1  2  3  5  6  7  8  9  4  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 7  1  2  5  4  3  6  9  8  0  
interim:  1  7  2  5  4  3  6  9  8  0  
interim:  1  2  7  5  4  3  6  9  8  0  
interim:  1  2  5  7  4  3  6  9  8  0  
interim:  1  2  4  5  7  3  6  9  8  0  
interim:  1  2  3  4  5  7  6  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  8  9  0  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Merge Testing
l1 = 0  2  3  4  6  7  9  
l2 = 1  3  5  8  10  
l3 = merge(l1,l2) = 0  1  2  3  3  4  5  6  7  8  9  10  


merge sort
unsorted: 6  9  0  8  7  2  3  1  4  5  
interim:  6  9  
interim:  0  
interim:  0  6  9  
interim:  7  8  
interim:  0  6  7  8  9  
interim:  2  3  
interim:  1  
interim:  1  2  3  
interim:  4  5  
interim:  1  2  3  4  5  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

If you haven't done so already you should at the very least download the AP Computer Science A Course Description. It's a PDF file and basically goes over everything you should have been taught in AP Computer Science (See References). My read of the latest 2010 document indicates that you only need to know about the 3 sorts I have covered. However in years past looking at the teaching site Bubble sort and Quick sort have been taught in the past. If you have time go over those your teacher's may have introduced them to you. If not then take the College Board at their word and make sure you know the 3 I have presented. For Future knowledge Donald Knuth in his Art of Computer Programming series goes over the following sorts (based on a quick scan of the text I may have missed one or two):

  • Insertion sort
  • Shell Sort
  • Exchange Sort
  • Bubble Sort
  • Baucher Sort
  • Quick Sort
  • Heap Sort
  • Merge Sort

If you go online to Google Scholar you will find many more. Sorting is certainly a basic problem for any Computer Scientist. They all have their drawbacks and the best one changes from time to time as people discover scenarios where the algorithms don't work well. In my day of learning this material I was told that Quicksort was best in actual practice even though theoretically Heap sort should have the better outcome. I don't have a reference for you but if you continue your pursuit of computers you will probably come across Journal articles that will espouse one algorithm over another.

References

  1. Knuth, Donald Ervin. The Art of Computer Programming Sorting and Searching. 2nd ed. Vol. 3. Reading, Mass. Addison-Wesley, 1998.
  2. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

Posted by at
Labels: , , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)