Created
September 5, 2018 14:06
-
-
Save sravanthi17/e85e65ae7e928eea4e55cbf62ec4fdbe to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.company; | |
import java.util.Scanner; | |
public class MergeSort2 { | |
static int[] input; | |
public static void main(String[] args) { | |
// write your code here | |
System.out.println("Please enter the size of array"); | |
Scanner scanner = new Scanner(System.in); | |
int size = scanner.nextInt(); | |
input = new int[size + 1]; | |
int i = 1; | |
System.out.println("Please enter elements in an array"); | |
while (i <= size) { | |
input[i] = scanner.nextInt(); | |
i++; | |
} | |
mergeSort2(1, size); | |
System.out.println("----Sorted array----"); | |
for (int j = 1; j <= size; j++) { | |
System.out.println(input[j]); | |
} | |
} | |
private static void mergeSort2(int low, int high) { | |
int mid; | |
if (low < high) { | |
mid = (low + high) / 2; | |
mergeSort2(low, mid); | |
mergeSort2(mid + 1, high); | |
merge2(low, mid, high); | |
} | |
} | |
private static void merge2(int low, int mid, int high) { | |
int i = low, j= mid +1, k = low, sourcePointer, destinationPointer; | |
int[] mergedArray = new int[high+low]; | |
while (i <= mid && j <= high) { | |
if (input[i] < input[j]) { | |
mergedArray[k] = input[i]; | |
i++; | |
} else { | |
mergedArray[k] = input[j]; | |
j++; | |
} | |
k++; | |
} | |
if (i > mid) { | |
sourcePointer = j; | |
destinationPointer = k; | |
while (sourcePointer <= high && destinationPointer <= high) { | |
mergedArray[destinationPointer] = input[sourcePointer]; | |
sourcePointer++; | |
destinationPointer++; | |
} | |
} else { | |
sourcePointer = i; | |
destinationPointer = k; | |
while (sourcePointer <= mid && destinationPointer <= high) { | |
mergedArray[destinationPointer] = input[sourcePointer]; | |
sourcePointer++; | |
destinationPointer++; | |
} | |
} | |
sourcePointer = low; | |
destinationPointer = low; | |
while (sourcePointer <= high && destinationPointer <= high) { | |
input[destinationPointer] = mergedArray[sourcePointer]; | |
sourcePointer++; | |
destinationPointer++; | |
} | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment