Mergesort in Java using divide and conquer

Posted By: Java Examples - 1:28 PM

Share

& Comment


Merge sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two collections and these are again sorted via mergesort. Once the two collections are sorted then the result is combined .Merge sort will take the middle of the collection and takes then the two collection for the next iteration of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of the both to insert it into a new collection.In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while mergesort requires a copy.


Thanks Wikipedia
Algorithm :
Conceptually, a merge sort works as follows
  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly Merge sub lists to produce new sublists until there is only 1 sublist remaining. (This will be the sorted list.)


Java version of the Mergesort is given below:



16
824412202826101418222630

Array of integers, named array

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Index of array element




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

package mergesort;

/**
 *
 * @author ACHCHUTHAN
 */
public class MergeSort {
    int array[];
    int size;

    public MergeSort(int n) {
        size=n;
        //create array with size n
        array=new int[n];
        //asign value into the array
        for (int i=0;i<n;i++){
            array[i]=(int) Math.round(Math.random()*89+10);
        }
    }

    public int getSize() {
        return size;
    }
    

    public void merge(int left, int mid, int right) {
        int temp [] =new int[right-left+1];
        int i = left;
        int j = mid+1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k] = array[i];
                k++;
                i++;
            } else { //array[i]>array[j]
                temp[k] = array[j];
                k++;
                j++;
            }
        }
        while(j<=right) temp[k++]=array[j++];
        while(i<=mid) temp[k++]=array[i++];

        for(k=0;k<temp.length;k++) array[left+k]=temp[k];
    }
    public void merge_sort(int left,int right){
        // Check if low is smaller then high, if not then the array is sorted
        if(left<right){
            // Get the index of the element which is in the middle
            int mid=(left+right)/2;
            // Sort the left side of the array
            merge_sort(left,mid);
            // Sort the right side of the array
            merge_sort(mid+1,right);
            // Combine them both
            merge(left,mid,right);
        }

    }
    public void print(){
        System.out.println("Contents of the Array");
        for(int k=0;k<15;k++) {
            System.out.print(array[k]+" | ");
        }
        System.out.println();

    }
    public static void main(String args[]){
        MergeSort m=new MergeSort(15);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        m.print();
        m.merge_sort(0,m.getSize()-1);
        System.out.println("After Sort > > > > > > > > > > > >");
        m.print();
        System.out.println("=======+============+=======+============+=========");
        MergeSort m2=new MergeSort(25);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        m2.print();
        m2.merge_sort(0,m2.getSize()-1);
        System.out.println("After Sort > > > > > > > > > > > >");
        m2.print();
        System.out.println("=======+============+=======+============+=========");
        MergeSort m3=new MergeSort(30);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        m3.print();
        m3.merge_sort(0,m3.getSize()-1);
        System.out.println("After Sort > > > > > > > > > > > >");
        m3.print();
        System.out.println("=======+============+=======+============+=========");

}
}
Output of this program 
run:
Before Sort <<<<<<<<<<<<<<<<<<<<< 
Contents of the Array 
59 | 42 | 28 | 34 | 95 | 72 | 48 | 27 | 46 | 20 | 28 | 61 | 25 | 81 | 30 | After Sort > > > > > > > > > > > >
Contents of the Array 
20 | 25 | 27 | 28 | 28 | 30 | 34 | 42 | 46 | 48 | 59 | 61 | 72 | 81 | 95 | 
 =======+============+=======+============+========= 
Before Sort <<<<<<<<<<<<<<<<<<<<< 
Contents of the Array 16 
| 67 | 78 | 34 | 50 | 26 | 79 | 82 | 35 | 44 | 72 | 97 | 69 | 55 | 47 | 
After Sort > > > > > > > > > > > >
Contents of the Array 10 | 16 | 18 | 26 | 27 | 30 | 34 | 35 | 44 | 44 | 47 | 50 | 55 | 56 | 67 | =======+============+=======+============+========= 
Before Sort <<<<<<<<<<<<<<<<<<<<< 
Contents of the Array 95 | 49 | 74 | 29 | 56 | 77 | 26 | 92 | 19 | 28 | 21 | 20 | 97 | 19 | 82 |
After Sort > > > > > > > > > > > > 
Contents of the Array 19 | 19 | 20 | 21 | 26 | 28 | 29 | 30 | 38 | 43 | 48 | 49 | 52 | 56 | 62 | =======+============+=======+============+========= 
BUILD SUCCESSFUL (total time: 0 seconds)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .