Scribd
Upload
6 views1 page

Merge Sort for Large Arrays in Java

The document provides a Java program for performing merge sort on an array of size 10^9, highlighting the impracticality of sorting such a large array on a 16 GB RAM laptop due to high memory and time requirements. It concludes that sorting 50 million elements is feasible, requiring significantly less memory and time. A result table summarizes the execution time and space required for both input sizes.

Uploaded by

pcmhacker511
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Merge Sort for Large Arrays in Java

The document provides a Java program for performing merge sort on an array of size 10^9, highlighting the impracticality of sorting such a large array on a 16 GB RAM laptop due to high memory and time requirements. It concludes that sorting 50 million elements is feasible, requiring significantly less memory and time. A result table summarizes the execution time and space required for both input sizes.

Uploaded by

pcmhacker511
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Name: Prakash Chand Meena

Roll No: 24BCS105

P1. Write a program (C/C++/JAVA/Python) to perform merge sorting on an array of size 10^9.
Create an array that occupies 10^9 elements and fill it with random values using the random
number generator function.

Java Code:
import [Link].*;

public class mergeSort {


public static void main(String[] args) {
int n = 1000000000; // For testing use smaller value like 50_000_000
int[] nums = new int[n];
Random rn = new Random();
for (int i = 0; i < n; i++) {
nums[i] = [Link](n);
}
long start = [Link]();
sort(nums, 0, [Link] - 1);
long end = [Link]();
[Link]("Execution Time: " + (end - start) + " ms");
}

private static void sort(int[] nums, int start, int end) {


if (start >= end) return;
int mid = start + (end - start) / 2;
sort(nums, start, mid);
sort(nums, mid + 1, end);
merge(nums, start, mid, end);
}

private static void merge(int[] nums, int start, int mid, int end) {
int i = start, j = mid + 1, k = 0;
int[] arr = new int[end - start + 1];

while (i <= mid && j <= end) {


if (nums[i] <= nums[j]) arr[k++] = nums[i++];
else arr[k++] = nums[j++];
}
while (i <= mid) arr[k++] = nums[i++];
while (j <= end) arr[k++] = nums[j++];

for (int l = 0; l < [Link]; l++) nums[start + l] = arr[l];


}
}

Q1. Can sorting be done correctly for the above input?

- For 1 Billion (10^9) elements: Sorting is not practical on a 16 GB RAM laptop because it requires
~8–12 GB memory and takes ~20–40 minutes (or may not complete).
- For 50 Million (5×10^7) elements: Sorting is feasible. It requires ~400–500 MB memory and takes
about 30 seconds to 2 minutes.

Result Table:
| Input Size | Execution Time Required | Space Required |
|--------------|-----------------------------------|-------------------|
| 1 Billion | ~20–40 minutes (impractical) | ~8–12 GB (not feasible) |
| 50 Million | ~30 sec – 2 min (practical) | ~400–500 MB |

You might also like