Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Created by MOHIT on 01-10-2017.
- */
- import java.util.Scanner;
- // program to implement recursive merge sort algorithm in c++
- public class merge_sort {
- static Scanner sc = new Scanner(System.in);
- // function that prints list of elements
- static void displayList(int elementList[], int length){
- for(int index = 0; index < length; index++){
- System.out.print(elementList[index] + " ");
- }
- System.out.println("\n");
- }
- // function that sorts and merges the list
- static void Merge(int[] data, int left, int middle, int right) {
- int i, j, k;
- // storing the left and the right list length
- int leftLength = middle - left + 1;
- int rightLength = right - middle;
- //creating 2 dummy lists to hold the split lists
- int[] leftTemp = new int[leftLength];
- int[] rightTemp = new int[rightLength];
- for (i = 0; i < leftLength; i++)
- leftTemp[i] = data[left + i];
- for (j = 0; j < rightLength; j++)
- rightTemp[j] = data[middle + 1 + j];
- // sorting and merging the left and right lists by element wise comparison
- i = 0;
- j = 0;
- k = left;
- while (i < leftLength && j < rightLength)
- {
- if (leftTemp[i] <= rightTemp[j])
- {
- data[k] = leftTemp[i];
- i++;
- }
- else
- {
- data[k] = rightTemp[j];
- j++;
- }
- k++;
- }
- while (i < leftLength)
- {
- data[k] = leftTemp[i];
- i++;
- k++;
- }
- while (j < rightLength)
- {
- data[k] = rightTemp[j];
- j++;
- k++;
- }
- }
- static int[] MergeSortRecursive(int[] data, int left, int right) {
- if (left < right)
- {
- int middle = left + (right - left) / 2;
- MergeSortRecursive(data, left, middle);
- MergeSortRecursive(data, middle + 1, right);
- Merge(data, left, middle, right);
- }
- return data;
- }
- public static void main(String arg[]){
- int length, element;
- int[] myList;
- System.out.println("Program to implement Recursive Merge sort algorithm in Java");
- System.out.println("Enter the number of Elements to be sorted : ");
- length = sc.nextInt();
- myList = new int[length];
- System.out.println("Enter the elements to be sorted : ");
- for(int index = 0; index < length; index++){
- element = sc.nextInt();
- myList[index] = element;
- }
- System.out.println("\nThe list of elements before sorting is : ");;
- displayList(myList, length);
- myList = MergeSortRecursive(myList, 0, length-1);
- System.out.println("\nThe sorted list is : ");
- displayList(myList, length);
- }
- }
Add Comment
Please, Sign In to add comment