Could someone explain each line of code? Especially the loops . /* Java program

Question

Could someone explain each line of code? Especially the loops.

/* Java program for Merge Sort */
class MergeSort
{
  
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;

int L[] = new int [n1];
int R[] = new int [n2];

for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];



int i = 0, j = 0;

int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2;

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

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

static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("Given Array");
printArray(arr);

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

System.out.println(" Sorted array");
printArray(arr);
}
}

Explanation / Answer

static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

This function is for printing the array.The loop is printing the elements of the arrau.

void sort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2;

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

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

This function does the sorting.It takes an array as an input along with the start index and end index also.It divides the list into two parts as
m = (l+r)/2

It then sorts individual lists(i.e sort(arr, l, m) and sort(arr , m+1, r);) and then merge them together.

void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;

int L[] = new int [n1];
int R[] = new int [n2];

for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];



int i = 0, j = 0;

int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

This function is actually merging the two sorted lists. So it first create two separate lists from the given list. These lists are getting formed in the for loop in the function (i.e L & R). After forming the two lists it merges them together which is happening in the while loops. Merging is happening in the following way:

The two indexex are assigned to L and R (i.e i to L and j to R). Two elements L[i] and R[j] are compared together, which ever is smaller will go to the resulting array and its corresponding index will be incremented. Once any one of the list gets finished , the other will be simpley copied to the resultant array.This is happeing in the last two while loops in the functuion. There are two loops because L can get finished, R will be copied or if R gets finished then L will be copied.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects