merge sort java code example

Example 1: merge sort java

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];
 
    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);
 
    merge(a, l, r, mid, n - mid);
}

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
 
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Example 2: merge sort c#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Merge_sort
{    
    class Program
    {
        static void Main(string[] args)
        {
            List<int> unsorted = new List<int>();
            List<int> sorted;

            Random random = new Random();

            Console.WriteLine("Original array elements:" );
            for(int i = 0; i< 10;i++){
                unsorted.Add(random.Next(0,100));
                Console.Write(unsorted[i]+" ");
            }
            Console.WriteLine();

            sorted = MergeSort(unsorted);

            Console.WriteLine("Sorted array elements: ");
            foreach (int x in sorted)
            {
                Console.Write(x+" ");
            }
			Console.Write("\n");
        }
		

        private static List<int> MergeSort(List<int> unsorted)
        {
            if (unsorted.Count <= 1)
                return unsorted;

            List<int> left = new List<int>();
            List<int> right = new List<int>();

            int middle = unsorted.Count / 2;
            for (int i = 0; i < middle;i++)  //Dividing the unsorted list
            {
                left.Add(unsorted[i]);
            }
            for (int i = middle; i < unsorted.Count; i++)
            {
                right.Add(unsorted[i]);
            }

            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }

        private static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>();

            while(left.Count > 0 || right.Count>0)
            {
                if (left.Count > 0 && right.Count > 0)
                {
                    if (left.First() <= right.First())  //Comparing First two elements to see which is smaller
                    {
                        result.Add(left.First());
                        left.Remove(left.First());      //Rest of the list minus the first element
                    }
                    else
                    {
                        result.Add(right.First());
                        right.Remove(right.First());
                    }
                }
                else if(left.Count>0)
                {
                    result.Add(left.First());
                    left.Remove(left.First());
                }
                else if (right.Count > 0)
                {
                    result.Add(right.First());

                    right.Remove(right.First());    
                }    
            }
            return result;
        }
    }
}

Example 3: how to write a merge sort array method ni java

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];
 
    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);
 
    merge(a, l, r, mid, n - mid);
}

Example 4: 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);
   }
}

Example 5: how to write a merge sort array method ni java

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
  
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

Example 6: merge sort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function merge(list, start, midpoint, end) {
    const left = list.slice(start, midpoint);
    const right = list.slice(midpoint, end);
    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
        if (topLeft >= left.length) {
            list[i] = right[topRight++];
        } else if (topRight >= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] < right[topRight]) {
            list[i] = left[topLeft++];
        } else {
            list[i] = right[topRight++];
        }
    }
}

function mergesort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length;
    }
    if (end - start > 1) {
        const midpoint = ((end + start) / 2) >> 0;
        mergesort(list, start, midpoint);
        mergesort(list, midpoint, end);
        merge(list, start, midpoint, end);
    }
    return list;
}

mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

Tags:

Java Example

Recent Posts