Question

Please answer in Java for an immediate upvote :)

1. Given the following array of 8 elements, trace the merge sort algorithm. Assume the array is to be sorted in ascending order.

                       81          16          4        6             34          11          23        67

ANSWER: (Hint 6 – lines):

1. Why don’t we select the median element of all the n-entries in the array to be our pivot point?

ANSWER:

Answer 1

SOLUTION

TRACING ALGORITHM

81	16	4	6	34	11	23	67
16	81	4	6	34	11	23	67
4	6	16	81	34	11	23	67
4	6	16	81	11	34	23	67
4	6	16	81	11	23	34	67
4	6	11	16	23	34	67	81

Why don’t we select the median element of all the n-entries in the array to be our pivot point?

It will needrsorting the array & getting the value in the middle.

The main goal is to sorting the array,

If we select the element we have a chance to end up with circular logic

Program

class Main {
  
void merge(int array[], int left, int m, int right)
{
  
int num1 = m - left + 1;
int num2 = right - m;
  
  
int Left[] = new int[num1];
int Right[] = new int[num2];
  
  
for (int i = 0; i < num1; ++i)
Left[i] = array[left + i];
for (int j = 0; j < num2; ++j)
Right[j] = array[m + 1 + j];
  
  
  

int i = 0, j = 0;
  
  
int k = left;
while (i < num1 && j < num2) {
if (Left[i] <= Right[j]) {
array[k] = Left[i];
i++;
}
else {
array[k] = Right[j];
j++;
}
k++;
}
  

while (i < num1) {
array[k] = Left[i];
i++;
k++;
}
  
/* Copy remaining elements of Right[] if any */
while (j < num2) {
array[k] = Right[j];
j++;
k++;
}
}
  

void sort(int array[], int left, int right)
{
if (left < right) {
  
int m = (left + right) / 2;
  
  
sort(array, left, m);
sort(array, m + 1, right);
  

merge(array, left, m, right);
}
}
  
  
static void printarrayay(int array[])
{
int n = array.length;
for (int i = 0; i < n; ++i)
System.out.print(array[i] + " ");
System.out.println();
}
  

public static void main(String args[])
{
int array[] = { 81,16,4,6,34,11,23,67 };
  
System.out.println("Given arrayay");
printarrayay(array);
  
Main obj = new Main();
obj.sort(array, 0, array.length - 1);
  
System.out.println("\nSorted arrayay");
printarrayay(array);
}
}

Output