Answers for "merge sort example"

merge sort in python

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)

merge sort

//merge sort
#include <iostream>

using namespace std;
void merge(int arr[],int start,int mid,int end)
{
    int n1=mid-start+1;
    int n2=end-mid;
    int l[n1],m[n2];
    for(int i=0;i<n1;i++)
    {
        l[i]=arr[start+i];
    }
    for(int j=0;j<n2;j++)
    {
        m[j]=arr[mid+1+j];
    }
    int i=0;
    int j=0;
    int k=start;
    while(i<n1&&j<n2)
    {
        if(l[i]<m[j])
        {
            arr[k]=l[i];
            k++;
            i++;
        }
        else
        {
            arr[k]=m[j];
            k++;
            j++;
        }
    }
    while(i<n1)
    {
        arr[k]=l[i];
        k++;
        i++;
    }
    while(j<n2)
    {
        arr[k]=m[j];
        k++;
        j++;
    }
}
void mergesort(int arr[],int start,int end)
{
    if(start<end)
    {
        int mid=(start+end)/2;
        mergesort(arr,start,mid);
        mergesort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
}
void display(int arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    int n;
    cout<<"enter the size of the array:"<<endl;
    cin>>n;
    cout<<"enter the elements of the array:"<<endl;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    cout<<"array as it is:"<<endl;
    display(arr,n);
    cout<<"sorted array:"<<endl;
    mergesort(arr,0,n-1);
    display(arr,n);
    return 0;
}

merge sort

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Merge sort

class Sort 
{
    void merge(int arr[], int left, int middle, int right)
    {
        int low = middle - left + 1;                    //size of the left subarray
        int high = right - middle;                      //size of the right subarray
 
        int L[] = new int[low];                             //create the left and right subarray
        int R[] = new int[high];

        int i = 0, j = 0;
 
        for (i = 0; i < low; i++)                               //copy elements into left subarray
        {
            L[i] = arr[left + i];
        }
        for (j = 0; j < high; j++)                              //copy elements into right subarray
        {
            R[j] = arr[middle + 1 + j];
        }
        
 
        int k = left;                                           //get starting index for sort
        i = 0;                                             //reset loop variables before performing merge
        j = 0;

        while (i < low && j < high)                     //merge the left and right subarrays
        {
            if (L[i] <= R[j]) 
            {
                arr[k] = L[i];
                i++;
            }
            else 
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        while (i < low)                             //merge the remaining elements from the left subarray
        {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        while (j < high)                           //merge the remaining elements from right subarray
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 

    void mergeSort(int arr[], int left, int right)       //helper function that creates the sub cases for sorting
    {
        int middle;
        if (left < right) {                             //sort only if the left index is lesser than the right index (meaning that sorting is done)
            middle = (left + right) / 2;
 
            mergeSort(arr, left, middle);                    //left subarray
            mergeSort(arr, middle + 1, right);               //right subarray
 
            merge(arr, left, middle, right);                //merge the two subarrays
        }
    }
 
    void display(int arr[])                 //display the array
    {  
        for (int i=0; i<arr.length; ++i) 
        {
            System.out.print(arr[i]+" ");
        } 
    } 

    public static void main(String args[])
    {
        int arr[] = { 9, 3, 1, 5, 13, 12 };
        Sort ob = new Sort();
        ob.mergeSort(arr, 0, arr.length - 1);
        ob.display(arr);
    }
}

Merge sort java

public class JavaMergeSort
{
   void sorting(int[] num, int left, int main, int right)
   {
      // finding size of two sub arrays
      int list1 = main - left + 1;
      int list2 = right - main;
      // creating temporary array
      int[] L = new int[list1];
      int[] R = new int[list2];
      // copying data to temporary array
      for(int a = 0; a < list1; ++a)
         L[a] = num[left + a];
      for(int b = 0; b < list2; ++b)
         R[b] = num[main + 1+ b];
      // existing index of first and second sub array
      int p = 0, q = 0;
      // existing index of merged sub array
      int r = left;
      while(p < list1 && q < list2)
      {
         if(L[p] <= R[q])
         {
            num[r] = L[p];
            p++;
         }
         else
         {
            num[r] = R[q];
            q++;
         }
         r++;
      }
      // copying remaining elements of L[] array
      while(p < list1)
      {
         num[r] = L[p];
         p++;
         r++;
      }
      // copying remaining elements of R[] array
      while(q < list2)
      {
         num[r] = R[q];
         q++;
         r++;
      }
   }
   // function that sorts
   void sort(int[] arrNum, int l, int r)
   {
      if(l < r)
      {
         // finding middle point
         int m = (l + r) / 2;
         // sorting first and second list
         sort(arrNum, l, m);
         sort(arrNum , m+1, r);
         // merging sorted list
         sorting(arrNum, l, m, r);
      }
   }
   // display array
   static void displayArray(int[] arr)
   {
      int number = arr.length;
      for(int a = 0; a < number; ++a)
         System.out.print(arr[a] + " ");
      System.out.println();
   }
   public static void main(String[] args)
   {
      int[] arrNumbers = {33, 00, 55, 11, 22, 44};
      System.out.println("Before sorting - ");
      displayArray(arrNumbers);
      JavaMergeSort obj = new JavaMergeSort();
      obj.sort(arrNumbers, 0, arrNumbers.length - 1);
      System.out.println("\nAfter sorting - ");
      displayArray(arrNumbers);
   }
}

merge sort

void merge(int arr[], int l, int m, int r)
    {
         int n=r-l+1,temp[n];
         int i=l,j=m+1,k=0;
         while(i<=m and j<= r)
         {
             if(arr[i]< arr[j]){
                temp[k++] = arr[i++];
             else
                temp[k++] = arr[j++];
         }
         while(i<=m)
            temp[k++] = arr[i++];
         while(j<=r)
            temp[k++] = arr[j++];
         int ind= 0;
         for(int i=l;i<=m;i++)
             arr[i] = temp[ind++];
         for(int j=m+1;j<=r;j++)
            arr[j] = temp[ind++];
    }
    
    void mergeSort(int arr[], int l, int r)
    {
       if(l<r)
       {
           int mid = (r+l)/2;
           mergeSort(arr,l,mid);
           mergeSort(arr,mid+1,r);
           merge(arr,l,mid,r);
       }
    }