m2skills

merge sort java

Oct 13th, 2017
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.98 KB | None | 0 0
  1. /**
  2.  * Created by MOHIT on 01-10-2017.
  3.  */
  4. import java.util.Scanner;
  5. // program to implement recursive merge sort algorithm in c++
  6. public class merge_sort {
  7.     static Scanner sc = new Scanner(System.in);
  8.  
  9.     // function that prints list of elements
  10.     static void displayList(int elementList[], int length){
  11.         for(int index = 0; index < length; index++){
  12.             System.out.print(elementList[index] + " ");
  13.         }
  14.         System.out.println("\n");
  15.     }
  16.  
  17.     // function that sorts and merges the list
  18.     static void Merge(int[] data, int left, int middle, int right) {
  19.         int i, j, k;
  20.  
  21.         // storing the left and the right list length
  22.         int leftLength = middle - left + 1;
  23.         int rightLength = right - middle;
  24.  
  25.         //creating 2 dummy lists to hold the split lists
  26.         int[] leftTemp = new int[leftLength];
  27.         int[] rightTemp = new int[rightLength];
  28.  
  29.         for (i = 0; i < leftLength; i++)
  30.             leftTemp[i] = data[left + i];
  31.  
  32.         for (j = 0; j < rightLength; j++)
  33.             rightTemp[j] = data[middle + 1 + j];
  34.  
  35.         // sorting and merging the left and right lists by element wise comparison
  36.         i = 0;
  37.         j = 0;
  38.         k = left;
  39.  
  40.         while (i < leftLength && j < rightLength)
  41.         {
  42.             if (leftTemp[i] <= rightTemp[j])
  43.             {
  44.                 data[k] = leftTemp[i];
  45.                 i++;
  46.             }
  47.             else
  48.             {
  49.                 data[k] = rightTemp[j];
  50.                 j++;
  51.             }
  52.  
  53.             k++;
  54.         }
  55.  
  56.         while (i < leftLength)
  57.         {
  58.             data[k] = leftTemp[i];
  59.             i++;
  60.             k++;
  61.         }
  62.  
  63.         while (j < rightLength)
  64.         {
  65.             data[k] = rightTemp[j];
  66.             j++;
  67.             k++;
  68.         }
  69.     }
  70.  
  71.     static int[] MergeSortRecursive(int[] data, int left, int right) {
  72.         if (left < right)
  73.         {
  74.             int middle = left + (right - left) / 2;
  75.  
  76.             MergeSortRecursive(data, left, middle);
  77.             MergeSortRecursive(data, middle + 1, right);
  78.             Merge(data, left, middle, right);
  79.         }
  80.         return data;
  81.     }
  82.  
  83.     public static void main(String arg[]){
  84.  
  85.         int length, element;
  86.         int[] myList;
  87.  
  88.         System.out.println("Program to implement Recursive Merge sort algorithm in Java");
  89.         System.out.println("Enter the number of Elements to be sorted : ");
  90.  
  91.         length = sc.nextInt();
  92.         myList = new int[length];
  93.  
  94.         System.out.println("Enter the elements to be sorted : ");
  95.         for(int index = 0; index < length; index++){
  96.             element = sc.nextInt();
  97.             myList[index] = element;
  98.         }
  99.  
  100.         System.out.println("\nThe list of elements before sorting is : ");;
  101.         displayList(myList, length);
  102.  
  103.         myList = MergeSortRecursive(myList, 0, length-1);
  104.  
  105.         System.out.println("\nThe sorted list is : ");
  106.         displayList(myList, length);
  107.     }
  108. }
Add Comment
Please, Sign In to add comment