java-coding-ninjas/recursion2/MergeSort.java at patch-2 · arshali2774/java-coding-ninjas · GitHub

History

76 lines (70 loc) · 2.79 KB

Raw

package recursion2;

import java.util.Scanner;

public class MergeSort {

public static void merge(int[] arr, int startIndex, int midIndex, int endIndex) {

//Calculating the size of the leftSubArray and rightSubArray

int n1 = midIndex - startIndex + 1;

int n2 = endIndex - midIndex;

//Creating arrays leftSubArray[0,1,2,- - -,(n1+1)] and rightSubArray[0,1,2,- - -,(n2+1)]

int[] leftSubArray = new int[n1 + 1];

int[] rightSubArray = new int[n2 + 1];

//Copying elements of the array from original array to left and right sub array

for (int i = 0; i < n1; i++) {

leftSubArray[i] = arr[startIndex + i];

}

for (int j = 0; j < n2; j++) {

rightSubArray[j] = arr[midIndex + j + 1];

}

//Making last element of the array be Infinite

leftSubArray[n1] = Integer.MAX_VALUE;

rightSubArray[n2] = Integer.MAX_VALUE;

//Counter for leftSubArray & rightSubArray respectively

int i = 0, j = 0;

//Comparing to sort and Merging the sub-arrays and copying into the original array

for (int k = startIndex; k <= endIndex; k++) {

if (leftSubArray[i] <= rightSubArray[j]) {

arr[k] = leftSubArray[i];

i++;

} else {

arr[k] = rightSubArray[j];

j++;

}

/*Merge-sort: Divide & Conquer -> Time Complexity(worst): O(n*logn), Space Complexity: O(n)*/

public static void mergeSort(int[] arr, int startIndex, int endIndex) {

if (startIndex < endIndex) {

int midIndex = (startIndex + endIndex) / 2;

//Dividing the array into 2 parts until we have only 1 element.

mergeSort(arr, startIndex, midIndex);

mergeSort(arr, midIndex + 1, endIndex);

//Merging the divided array into sorted order

merge(arr, startIndex, midIndex, endIndex);

}

public static int[] takeArrayInput() {

Scanner scan = new Scanner(System.in);

int size = scan.nextInt();

int[] arr = new int[size];

for (int i = 0; i < size; i++) {

/*arr[i] = scan.nextInt();*/

arr[i] = (int) Math.floor(Math.random() * (999 - 100 + 1) + 100);

}

return arr;

}

public static void printArray(int[] arr) {

for (int i : arr) {

System.out.print(i + "\t");

}

System.out.println();

}

public static void main(String[] args) {

System.out.println("Enter the size of the Array?");

int[] arr = takeArrayInput();

System.out.println("Array before sorting:");

printArray(arr);

mergeSort(arr, 0, arr.length - 1);

System.out.println("Array After sorting:");

printArray(arr);

}

java-coding-ninjas/recursion2/MergeSort.java at patch-2 · arshali2774/java-coding-ninjas · GitHub

Expand file tree

Breadcrumbs

MergeSort.java

Latest commit

History

Breadcrumbs

MergeSort.java

File metadata and controls