Wednesday, May 2, 2018

Merge Sort

import java.io.File;
import java.util.Arrays;
import java.util.Scanner;

/* File      :MergeSort.java 
* Author    :Prasanna Paudyal 
* Date      :05/02/2018 
* ----------------------------- 
* OVERVIEW * ======== 
* This is a simple program to 
* sort an array of numbers. This 
*  program does this by implementing  
*  the concept of Merge sort. 
*/ 
 
 public class MergeSort {
    public static void main(String[]args){
        int[] arr = new int[100];
        File file = new File(args[0]);
        try{
            Scanner scan = new Scanner(file);
            int i = 0;
            while(scan.hasNextLine()){
                String line = scan.nextLine();
                Scanner input = new Scanner(line);
                while(input.hasNext()){
                    String number = input.next();
                    int num = Integer.parseInt(number);
                    arr[i++] = num;
                }
                input.close();
            }
            scan.close();
        }catch(Exception e){
            System.err.println("File doesn't exist\n");
        }

        sort(arr);
 
 //print the sorted array 
 for(int i = 0; ilength;i++){
    System.out.printf("%d ",arr[i]);
    }
}

/** Merge sort algorithm 
 * @param arr: takes an array as an arguments and sorts them using merge sort 
*/  


public static void sort(int [] arr){
        if(arr.length <= 1){
            return;
        }
        //Split array into two 
        int middle = arr.length/2;
        int[] leftArray = Arrays.copyOfRange(arr,0,middle);
        int[] rightArray = Arrays.copyOfRange(arr, middle,arr.length);

        //Recursive call 
        sort(leftArray);
        sort(rightArray);

        // sort and build array back 
        int i = 0;
        int j = 0;
        while ((i +j)  < arr.length) {
            if (i < leftArray.length && j < rightArray.length) {
                if (leftArray[i] < rightArray[j]) {
                    arr[i + j] = leftArray[i];
                    i++;
                } else {
                    arr[i + j] = rightArray[j];
                    j++;
                }
            } else if (i < leftArray.length) {
                arr[i + j] = leftArray[i];
                i++;
            } else {
                arr[i + j] = rightArray[j];
                j++;
            }
        }

    }

}



/*
*Note: Find the test file for numbers here
*/ 

No comments: