13. mergesort merges the subarrays of an array that is already in order. Another

Question

13. mergesort merges the subarrays of an array that is already in order. Another top-down version of mergesort alleviates this problem by merging only runs, subarrays with ordered elements. Merging is applied only after two runs are determined. For example, in the array 16 7 8 3 4 1 11 12 13 2), runs 16 7 8] and 13 4] are first merged to become (3 4 6 7 8], then runs (1 11 12 13] and [2] are merged to become [1 2 11 12 13, and finally, runs 13 4 678 and [1211 12 13 are merged to become [1 2 3 4 6 7 8 11 12 13]. Implement this algorithm and investigate its complexity. A mergesort that takes advantage of a partial ordering of data (that is, uses the runs) is called a natural sort. A version that disregards the runs by always dividing arrays into (almost) even sections is referred to as straight merging. In orr sorted with mergesort

Explanation / Answer

Algorithem for MergeSort :-

MergeSort(array A, int p, int r)
{
   if (p < r)
   {
       q = (p + r)/2
       MergeSort(A, p, q)        // sort A[p..q]
       MergeSort(A, q+1, r)    // sort A[q+1..r]
       Merge(A, p, q, r)        // merge everything together
   }
}

Merge(array A, int p, int q, int r)
{ // merges A[p..q] with A[q+1..r]
   array B[p..r]
   i = k = p                        // initialize pointers
   j = q+1
   while (i <= q and j <= r)
   {                                // while both subarrays are nonempty
       if (A[i] <= A[j])
           B[k++] = A[i++]    // copy from left subarray
       else
           B[k++] = A[j++]    // copy from right subarray
   }
   while (i <= q)
       B[k++] = A[i++]       // copy any leftover to B
   while (j <= r)
       B[k++] = A[j++]
   for i = p to r do
       A[i] = B[i]        // copy B back to A
}

Program in Java :-

import java.util.Scanner;

class MergeSort
{
public static void sort(int[] arr, int low, int high)
{
int N = high - low;   
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort
sort(arr, low, mid);
sort(arr, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = arr[j++];
else if (j == high)
temp[k] = arr[i++];
else if (arr[j]<arr[i])
temp[k] = arr[j++];
else
temp[k] = arr[i++];
}
for (int k = 0; k < N; k++)
arr[low + k] = temp[k];   
}

public static void main(String[] args)
{
Scanner in= new Scanner( System.in );
System.out.println("Merge Sort Test ");
int n, i;

System.out.println("Enter number of vaues in list(size) :");
n = in.nextInt();

int list[] = new int[ n ];
  
System.out.println(" Enter "+ n +" values into array ");
for (i = 0; i < n; i++)
list[i] = in.nextInt();
          
       System.out.println(" Values before sorting ");
for (i = 0; i < n; i++)
System.out.print(list[i]+" ");

sort(list, 0, n);
/* Print sorted Array */
System.out.println(" Values after sorting ");
for (i = 0; i < n; i++)
System.out.print(list[i]+" ");
System.out.println();
}
}

Output :-

C:Users ajendraDocumentscheggjava>java MergeSort
Merge Sort Test

Enter number of vaues in list(size) :
10

Enter 10 values into array
6 7 8 3 4 1 11 12 13 2

Values before sorting
6 7 8 3 4 1 11 12 13 2
Values after sorting
1 2 3 4 6 7 8 11 12 13

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.