merge sort technique code example

Example 1: merge sort iterative (string)

//Joshua Khumalo
import java.util.Arrays;
public class Demo{
   public static void merge_sort(int[] my_arr){
      if(my_arr == null){
         return;
      }
      if(my_arr.length > 1){
         int mid = my_arr.length / 2;
         int[] left = new int[mid];
         for(int i = 0; i < mid; i++){
            left[i] = my_arr[i];
         }
         int[] right = new int[my_arr.length - mid];
         for(int i = mid; i < my_arr.length; i++){
            right[i - mid] = my_arr[i];
         }
         merge_sort(left);
         merge_sort(right);
         int i = 0;
         int j = 0;
         int k = 0;
         while(i < left.length && j < right.length){
            if(left[i] < right[j]){
               my_arr[k] = left[i];
               i++;
            } else {
               my_arr[k] = right[j];
               j++;
            }
            k++;
         }
         while(i < left.length){
            my_arr[k] = left[i];
            i++;
            k++;
         }
         while(j < right.length){
            my_arr[k] = right[j];
            j++;
            k++;
         }
      }
   }
   public static void main(String[] args){
      int my_arr[] = {56, 78, 91, 21, 34, 0, 11};
      int i=0;
      merge_sort(my_arr);
      System.out.println("The array after sorting is ");
      for(i=0; i<my_arr.length; i++)
      System.out.print(my_arr[i]+" ");
   }
}

Example 2: merge sort algo

def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 # Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
            k+= 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end =" ") 
    print() 
  
# driver code to test the above code 
if __name__ == '__main__': 
    arr = [12, 11, 13, 5, 6, 7]  
    print ("Given array is", end ="\n")  
    printList(arr) 
    mergeSort(arr) 
    print("Sorted array is: ", end ="\n") 
    printList(arr)

Example 3: merge sort algorithm

/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array. 
*/

#include <stdio.h>

// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.

// merge sort function
void mergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);
        merge(a, p, q, r);
    }
}

// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
    int b[5];   //same size of a[]
    int i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
        {
            b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
        }
        else
        {
            b[k++] = a[j++];
        }
    }
  
    while(i <= q)
    {
        b[k++] = a[i++];
    }
  
    while(j <= r)
    {
        b[k++] = a[j++];
    }
  
    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];  // copying back the sorted list to a[]
    } 
}

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
 
int main()
{
    int arr[] = {32, 45, 67, 2, 7};
    int len = sizeof(arr)/sizeof(arr[0]);
 
    printf("Given array: \n");
    printArray(arr, len);
    
    // calling merge sort
    mergeSort(arr, 0, len - 1);
 
    printf("\nSorted array: \n");
    printArray(arr, len);
    return 0;
}