Merge Sort Using Divide and Conquer

Algorithm

(Interview-Oriented Pseudocode)

This pseudocode is intended to help learners understand and explain the algorithm and develop their own solution.

Merge_Sort(A,p,r)
{
       if(p<r)
         q=[(p+r)/2]
         Merge_Sort(A,p,q)
         Merge_Sort(A,q+1,r)
         Merge(A,p,q,r)
}
Merge(A,p,q,r){
n1=q-p+1
n2=r-q
Let L[1...n1+1] and R[1....n2+1] be two new arrays
for(i=1 to n1)
     L[i]=A[i]
for(j=1 to n2)
     R[j]=A[j]
L[n1+1]=infinity(large number)
R[n2+1]=infinity(large number)
i=1,j=1
for(k=p to r)
     if(L[i]<R[j])
       A[k]=L[i]
       i=i+1
     else
        A[k]=R[j]
         j=j+1

Code

class mergesort{
    public static void main(String args[]){
        int arr[]={3,2,1,6,9};
        merge_sort(arr,0,arr.length-1);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
    static int[] merge_sort(int arr[],int p,int r){
        if(p<r){
            int q=((p+r)/2);
            merge_sort(arr, p, q);
            merge_sort(arr, q+1, r);
            merge(arr,p,q,r);
        }
        return arr;
    }
  static int[] merge(int arr[],int p,int q,int r){
    int n1=q-p+1;
    int n2=r-q;
    int L[]=new int[n1+1];
    int R[]=new int[n2+1];

    for(int i=0;i<n1;i++){
        L[i]=arr[p+i];

    }
    for(int j=0;j<n2;j++){
        R[j]=arr[q+j+1];
    }
    L[n1]=Integer.MAX_VALUE;
    R[n2]=Integer.MAX_VALUE;
    int i=0,j=0;
    for(int k=p;k<=r;k++){
        if(L[i]<R[j])
        {
            arr[k]=L[i];
            i++;
        }
        else{
            arr[k]=R[j];
            j++;
        }
    }
    return  arr;
   }
}

Output

1 2 3 6 9

Similar Topics

The main function takes user inputs for an array and a key to search for.The binarysearch function is a recursive implementation that splits the array in half, comparing the middle element to the key.It uses divide and conquer to narrow down the search range by half each time, making it efficient with O(log⁡n) time complexity.

Learn Quick Sort using Divide and Conquer in C along with Pseudo Code Algorithm.

Learn Binary Search Using Divide and Conquer in C, along with Pseudo Code and Algorithm.