Thread: Merge Sort Using Java

Forum : New To Java   14-12-2017 10:02:01 AM
User Image
Amritk

Newbie

Joined: May 8, 2017

Points: 230

Threads: 57

Posts: 211

Merge Sort Using Java

| Quote Date : Dec 14, 2017    Views:322    



Merge sort is a sorting algorithm that is based on divide and conquer concept.

A divide and conquer algorithm : Divide a problem into two or more sub-problems recursively, until these become simple enough to be solved directly.

Introduction:

Merge sort is sequence sorting algorithm. That takes help of recursive technique to split list or array into half and merge them at end.

Divide the unsorted list or array into two parts from the midpoint.
Sort the left half(recursively)
Sort the right half(recursively)
Merge the two sorted halves into one sorted list.

Example: If list or array have more than two elements then remove all the elements from list, and put them into two separate list1 and list2. Where list1 contains the first(n/2) elements and list2 contains the remaining (n/2) elements.

Now sort these two lists recursively.
And finally Put back these two list(list1 and list2) into original list, by merging the sorted list1 and list2.


public class MergeSort {
   
   
    public static int[] mergeSort(int [] list) {
        if (list.length <= 1) {
            return list;
        }
       
        // Split the array in half
        int[] first = new int[list.length / 2];
        int[] second = new int[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);
       
        // Sort each half
        mergeSort(first);
        mergeSort(second);
       
        // Merge the halves together, overwriting the original array
        merge(first, second, list);
        return list;
    }
   
    private static void merge(int[] first, int[] second, int [] result) {
        // Merge both halves into the result array
        // Next element to consider in the first array
        int iFirst = 0;
        // Next element to consider in the second array
        int iSecond = 0;
       
        // Next open position in the result
        int j = 0;
        // As long as neither iFirst nor iSecond is past the end, move the
        // smaller element into the result.
        while (iFirst < first.length && iSecond < second.length) {
            if (first[iFirst] < second[iSecond]) {
                result[j] = first[iFirst];
                iFirst++;
                } else {
                result[j] = second[iSecond];
                iSecond++;
            }
            j++;
        }
        // copy what's left
        System.arraycopy(first, iFirst, result, j, first.length - iFirst);
        System.arraycopy(second, iSecond, result, j, second.length - iSecond);
    }
   
   
   
   
   
    public static void main(String args[]) throws Exception
    {
        String list="";
        int i=0,n=0;
       
        MergeSort s= new MergeSort();
        List arrlist=new ArrayList();
        arrlist.add(2);
        arrlist.add(4);
        arrlist.add(34);
        arrlist.add(23);
        arrlist.add(43);
        arrlist.add(21);
       
        int elementlist[] = new int[arrlist.size()];
        Iterator iter = arrlist.iterator();
        for (int j=0;iter.hasNext();j++) {
            elementlist[j] = iter.next();
        }
       
        elementlist=mergeSort(elementlist);
       
        System.out.println("Values after Merge Sort : ");
        for (int j=0;j
            System.out.println(elementlist[j]+" ");
        }
    }
}

Points:
java.lang.System.arraycopy() method copies a source array from a specific beginning position to the destination array from the mentioned position.

When to use Merge Sort

case1: While storing bigger size file
 When sorting a file which doesn?t fit into memory,We break it into chunks which fit into memory, sort these using independently, writing each out to a file, then merge sort the generated files.


Please download attached file for more details. ?



Comments

User Image
ArifKhan

Newbie

Joined : Jun 25, 2017

Points : 175

Threads: 115

Posts: 94

Re: Merge Sort Using Java

Reply Date : Dec 15, 2017

Thank you..for your input..!!
Please provide us input for,  how to create our own ArrayList and HashMap..!!


Load More

No More Comments