Merge Sort (For, While, Recursion)
•
17 min read
Description
Merge sorting using for loops, while loops, and recursion
// RECURSION
import java.util.Random;
public class MergeSortR {
void merge(int arr[], int a, int b, int c) {
int indexA = b - a + 1;
int indexB = c - b;
int left[] = new int[indexA];
int right[] = new int[indexB];
for (int i = 0; i < indexA; ++i)
left[i] = arr[a + i];
for (int j = 0; j < indexB; ++j)
right[j] = arr[b + 1 + j];
int i = 0, j = 0;
int k = a;
while (i < indexA && j < indexB) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < indexA) {
arr[k] = left[i];
i++;
k++;
}
while (j < indexB) {
arr[k] = right[j];
j++;
k++;
}
}
void sort(int arr[], int a, int c) {
if (a < c) {
int b = (a + c) / 2;
sort(arr, a, b);
sort(arr, b + 1, c);
merge(arr, a, b, c);
System.out.println("Iteration: ");
printArray(arr);
}
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
static int[] generateRandomArray(int size) {
int[] arr = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(100); // numbers are from 0-99
}
return arr;
}
public static void main(String args[]) {
int size = 8; // array size
int[] arr = generateRandomArray(size);
System.out.println("Original: ");
printArray(arr);
MergeSortR ob = new MergeSortR();
ob.sort(arr, 0, arr.length - 1);
System.out.println("\nSorted: ");
printArray(arr);
}
}
MergeSortR.main(null)
Original:
29 86 76 83 3 50 77 81
Iteration:
29 86 76 83 3 50 77 81
Iteration:
29 86 76 83 3 50 77 81
Iteration:
29 76 83 86 3 50 77 81
Iteration:
29 76 83 86 3 50 77 81
Iteration:
29 76 83 86 3 50 77 81
Iteration:
29 76 83 86 3 50 77 81
Iteration:
3 29 50 76 77 81 83 86
Sorted:
3 29 50 76 77 81 83 86
// WHILE
import java.util.Arrays;
import java.util.Random;
public class MergeSortW {
public static void mergeSort(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
int value;
int leftStart;
for (value = 1; value < n; value *= 2) {
for (leftStart = 0; leftStart < n - 1; leftStart += 2 * value) {
int mid = Math.min(leftStart + value - 1, n - 1);
int rightEnd = Math.min(leftStart + 2 * value - 1, n - 1);
merge(arr, temp, leftStart, mid, rightEnd);
}
}
}
public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
System.out.println("Iteration: ");
printArray(arr);
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
static int[] randomArray(int size) {
int[] arr = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(100); // numbers are from 0-99
}
return arr;
}
public static void main(String[] args) {
int size = 8; //array size
int[] arr = randomArray(size);
System.out.println("Original: ");
printArray(arr);
mergeSort(arr);
System.out.println("\nSorted: ");
printArray(arr);
}
}
// FORMergeSortW.main(null)
Original:
14 7 88 52 21 56 37 53
Iteration:
7 14 88 52 21 56 37 53
Iteration:
7 14 52 88 21 56 37 53
Iteration:
7 14 52 88 21 56 37 53
Iteration:
7 14 52 88 21 56 37 53
Iteration:
7 14 52 88 21 56 37 53
Iteration:
7 14 52 88 21 37 53 56
Iteration:
7 14 21 37 52 53 56 88
Sorted:
7 14 21 37 52 53 56 88
// FOR
import java.util.Arrays;
import java.util.Random;
public class MergeSortF {
public static void mergeSort(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
for (int value = 1; value < n; value *= 2) {
for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * value) {
int mid = Math.min(leftStart + value - 1, n - 1);
int rightEnd = Math.min(leftStart + 2 * value - 1, n - 1);
merge(arr, temp, leftStart, mid, rightEnd);
}
}
}
public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
System.out.println("Iteration: ");
printArray(arr);
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
static int[] randomArray(int size) {
int[] arr = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(100); // numbers are from 0-99
}
return arr;
}
public static void main(String[] args) {
int size = 8; //array size
int[] arr = randomArray(size);
System.out.println("Original: ");
printArray(arr);
mergeSort(arr);
System.out.println("\nSorted: ");
printArray(arr);
}
}
MergeSortF.main(null)
Original:
55 52 24 72 38 69 33 58
Iteration:
52 55 24 72 38 69 33 58
Iteration:
52 55 24 72 38 69 33 58
Iteration:
52 55 24 72 38 69 33 58
Iteration:
52 55 24 72 38 69 33 58
Iteration:
24 52 55 72 38 69 33 58
Iteration:
24 52 55 72 33 38 58 69
Iteration:
24 33 38 52 55 58 69 72
Sorted:
24 33 38 52 55 58 69 72