Skip to content

Instantly share code, notes, and snippets.

@sravanthi17
Created September 5, 2018 14:06
Show Gist options
  • Save sravanthi17/e85e65ae7e928eea4e55cbf62ec4fdbe to your computer and use it in GitHub Desktop.
Save sravanthi17/e85e65ae7e928eea4e55cbf62ec4fdbe to your computer and use it in GitHub Desktop.
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