Merge Sort on array in BlueJ Programming

Merge sort may be of different types. Firstly we will do merge sort on two different arrays of same or different sizes. Actually merge sort is a technique of sorting elements where any kind of sorting technique can be used.

Suppose there are two arrays int a[] and int b[] of size 10 each. The technique that combines these two arrays is called merging. The arrays are to be sorted first and then they may be merged. It is also possible to merge them first and after that the sorting will be done.

Algorithm for sorting the two arrays first and then merging them

A and B are two arrays with n and m number of elements. Both the arrays are sorted first. C is the final array where the final values will be stored and in sorted order. I, J and K are three integer type variables with initial value 0 .They will be used as array index or the three arrays.

Repeat the following steps while ((I< n) and (J< m)) If A[I]< =B[J] C[K]=A[I] I=I+1 K=K+1 Else C[K]=B[J] J=J+1 K=K+1 End of If [End of loop] If I< n [means first array has more values ] Repeat the following steps for I=I,I+1…n-1 C[K]=A[I] I=I+1 K=K+1 [End of loop] Else If (J< m) Repeat the following steps for J=J,J+1…m-1 C[K]=B[J] J=J+1 K=K+1 [End of loop] End

Program on merge sort using two arrays

import java.io.*;

 class Merge

 {

  int a[],b[],c[],i,j,k;

  int temp,flag;

 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

 int n,m;

 public void take()throws Exception

 {

 System.out.println("\nEnter size of the first array:");

 n=Integer.parseInt(br.readLine());

 System.out.println("\nEnter size of the second array:");

 m=Integer.parseInt(br.readLine());

 a=new int[n];

 b=new int[m];

c=new int[n+m];

System.out.println("\nEnter values for first array:\n");

 for(i=0;i< n;i++)

 {

 System.out.println("\nEnter value:");

 a[i]=Integer.parseInt(br.readLine());

 }

System.out.println("\nEnter values for second array:\n");

 for(i=0;i< m;i++)

 {

 System.out.println("\nEnter value:");

 b[i]=Integer.parseInt(br.readLine());

 }

 bsort();

 msort();

 display();

}

private void bsort()

{

int flag;

for(i = 0 ; i< n - 1; i++)

{

flag=0;

for(j = 0 ; j< n - i - 1 ; j++)

{

if(a[j] > a[j+1])

{

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp ;

flag = 1;

}

}

if(flag==0)

break ;

}

for(i = 0 ; i< m - 1; i++)

{

flag=0;

for(j = 0 ; j< m - i - 1 ; j++)

{

if(b[j] > b[j+1])

{

temp = b[j];

b[j] = b[j+1];

b[j+1] = temp ;

flag = 1;

}

}

if(flag==0)

break ;

}

}

private void  msort( )

{

int k = 0;

i = 0;

j = 0;

while((i< n) &&(j< m))

{

if(a[i]< =b[j])

{

c[k++] = a[i];

i++;

}

else

{

c[k++] = b[j];

j++;

}

}

if(i< n )

{

for( ; i< n ; i++)

{

c[k++] = a[i];

}

}

else if(j< m)

{

for(; j< m; j++)

{

c[k++] = b[j];

}

}

}

private void display()

{

 System.out.println("\nFirst array in sorted order\n");

 for(i=0 ; i< n ; i++)

 System.out.print(" " + a[i]);

 System.out.println("\nSecond array in sorted order\n");

 for(i=0 ; i< m ; i++)

 System.out.print(" " + b[i]);

 System.out.println("\nMerged sorted values\n");

 for(i=0 ; i< n+m ; i++)

 System.out.print(" " + c[i]);

}

public static void main(String args[])throws Exception

{

 Merge ob=new Merge();

 ob.take();

 }

 }

Analysis of the merge sort program in BlueJ

Four functions are defined in this merge sort program. ‘public void take()’ function takes the number of elements to be stored in two arrays and the three arrays are created. Values are stored in the two arrays and both the arrays are sorted in ascending order using the ‘private void bsort ()’ function. The third function ‘private void msort ()’ performs the merging job. In this program ‘n’ is the size of the first array and ‘m’ is the size of the second array. Two variables ‘i’ and ‘j’ are made to point the starting indexes of first array and the second array. In the while loop the condition set is ‘i< n && j< m’ which means any one of the condition will become false when the loop breaks. Inside the loop the checking condition is set to check if the value in the first array pointed by variable ‘I’ is less than or equal to the value in second array pointed by ‘j’. If the condition becomes true, the value from the first array is stored in the third array and the variable ‘I’ is incremented by 1 to point the next location value. If the condition becomes false, the same process is carried out on second array and the variable ‘j’ is incremented by 1. Any one of the variables ‘i’ or ‘j’ will reach the value ‘n’ or ‘m’ first and the loop will break. Next job of the program is to check from which condition the loop breaks. If the condition i< n becomes false, it means that all the values of the first array is stored in the final array ‘c’ and the elements from second array are to be accessed and to be stored in the third array. The reverse condition may also happen. ‘private void display ()’ function displays the arrays.

Merge Sort on single array

This merge sort is carried out on a single array. This sorting is called external sorting as number of temporary locations will be created and sorting process will take place in those external locations. After sorting, the sorted elements will be placed in the original array. Suppose there are 8 values in an array and the values are to be sorted using merge sort. The array list is to be divided into 4 sublist each of which contains 2 elements and the sublists are to be sorted. After sorting the sublists, two consecutive lists will be merged to form a new sublists. In our case 2 sublists will be formed and the sublists will be sorted again. The sorting technique can be selection sort, bubble sort or any other. Then again the sublists will be merged and sorting process will continue until it becomes a single list. Then finally the single list will be sorted.

Suppose values are:

66 33 40 22 55 88 60 11

The groups will be like
66 33 40 22 55 88 60 11
After sorting we get
33 66 22 40 55 88 11 60
Now the new group
33 66 22 40 55 88 11 60
After sorting
22 33 40 66 11 55 60 88
The new group
22 33 40 66 11 55 60 88
After sorting
11 22 33 40 55 60 66 88

Codes of the merge sort Program on single array

class MergeSingle

{

 void sort(int arr[],int top,int size,int bottom)

{

 int temp[]=new int[20];

 int f=top;

 int s=size+1;

 int t=top;

 int upper;

 while((f< =size)&&(s< =bottom))

 {

  if(arr[f]< =arr[s])

  {

                temp[t]=arr[f];

                f++;

                }

                else

                {

                 temp[t]=arr[s];

                 s++;

                }

                t++;

  }

  if(f<=size)

  {

                for(f=f;f< =size;f++)

                {

                 temp[t]=arr[f];

                 t++;

                 }

  }

  else

  {

                for(s=s;s< =bottom;s++)

                {

                 temp[t]=arr[s];

                 t++;

                }

  }

  for(upper=top;upper <=bottom;upper++)

  {

                arr[upper]=temp[upper];

  }

 }

 void pass(int arr[],int m,int n)

 {

  if(m!=n)

  {

                int mid=(m+n)/2;

                pass(arr,m,mid);

                pass(arr,mid+1,n);

                sort(arr,m,mid,n);

  }

 }

public static void main(String args[])

{

MergeSingle ob=new MergeSingle();

int list[]={22,1,23,3,43,4,3,2,55,4,5,6,7,11,12,23,45,67,8,9};

  int i;

  System.out.println("\nElements as follows\n");

  for(i=0;i< 20;i++)

  System.out.print(" "+list[i]);

  ob.pass(list,0,19);

  System.out.println("\nElements after sorting---as follows\n");

  for(i=0;i< 20;i++)

  System.out.print(" "+list[i]);

}

}

N.B:- This merge sort on single array is not for ISC and ICSE examination.