Scribd
Upload
22 views3 pages

Mergesort 1

The document presents a Java program for external sorting using the merge sort algorithm, which sorts an array of integers. It includes methods for merging subarrays, performing the merge sort, and printing the array. The program also captures user input for the number of elements and the elements themselves, displaying the array before and after sorting.

Uploaded by

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

Mergesort 1

The document presents a Java program for external sorting using the merge sort algorithm, which sorts an array of integers. It includes methods for merging subarrays, performing the merge sort, and printing the array. The program also captures user input for the number of elements and the elements themselves, displaying the array before and after sorting.

Uploaded by

kartiksomvanshi944
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

/*S.E.(A). Roll No.:47. Name: Aditi Sunil Gite .

Assignment no. 00: Assume we have two input and two output tapes to
perform the sorting. The internal memory can hold and sort m records at a
time. Write a program in Java for external sorting. Find out time
complexity. */

import java.util.Scanner;
class MergeSort
{

// Merge two subarrays L and M into arr


void merge(int arr[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1];
int M[] = new int[n2];

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


L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

// Maintain current index of sub-arrays and main array


int i, j, k;
i = 0;
j = 0;
k = p;

// Until we reach either end of either L or M, pick larger among


// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2)
{
if (L[i] <= M[j])
{
arr[k] = L[i];
i++;
} else
{
arr[k] = M[j];
j++;
}
k++;
}

// When we run out of elements in either L or M,


// pick up the remaining elements and put in A[p..r]
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

while (j < n2)


{
arr[k] = M[j];
j++;
k++;
}
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{

// m is the point where the array is divided into two subarrays


int m = (l + r) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted subarrays


merge(arr, l, m, r);
}
}

// Print the array


static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {

int n;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the number of elements you want to store:
");
//reading the number of elements from the that we want to enter
n=sc.nextInt();

int[] arr = new int[n];


System.out.println("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
//reading array elements from the user
arr[i]=sc.nextInt();
}
System.out.println("Enter Array before sorting");

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


printArray(arr);
MergeSort ob = new MergeSort();
ob.mergeSort(arr, 0, arr.length - 1);

System.out.println("Sorted array:");
printArray(arr);
}
}
/*
Output:
Enter the number of elements you want to store: 6
Enter the elements of the array:
45 12 78 34 23 10
Enter Array before sorting
Array before sorting
45 12 78 34 23 10
Sorted array:
10 12 23 34 45 78
*/

You might also like