Implementing Merge Sort Algorithm in Java

A merge sort works as follows:

  • Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  • Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Merge Sort Example
Merge Sort Example

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged. (Via Wikipedia)

import java.io.*;
class mergesort1 {

    public static void simplemerge(int a[], int f, int s, int t) {
        int i, j, k, w;
        int temp[] = new int[a.length];

        i = f;
        j = s;
        k = -1;

        while (i <= s - 1 && j <= t) {
            if (a[i] < a[j]) {
                k++;
                temp[k] = a[i];
                i++;

            } else {

                k++;
                temp[k] = a[j];
                j++;
            }
        }

        if (i > s - 1) {
            for (w = j; w <= t; w++) {
                k++;
                temp[k] = a[w];
            }
        } else {
            for (w = i; w <= s - 1; w++)

            {
                k++;
                temp[k] = a[w];

            }
        }

        for (w = 0; w <= k; w++)
            a[f + w] = temp[w];
    }


    public static void mergesort(int a[], int left, int right) {
        int mid;

        if (left < right) {
            mid = (left + right) / 2;
            mergesort(a, left, mid);
            mergesort(a, mid + 1, right);
            simplemerge(a, left, mid + 1, right);
        }

    }


    public static void main(String args[]) throws IOException {
        System.out.println("enter the number of elements");
        BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(kbd.readLine());


        int a[] = new int[n];

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

            System.out.println("enter elements" + (i + 1));
            a[i] = Integer.parseInt(kbd.readLine());

        }

        mergesort(a, 0, n - 1);

        for (int i = 0; i <= n - 1; i++)
            System.out.println(a[i]);
    }
}
/*
OUTPUT:
enter the number of elements

4
enter elements1

12
enter elements2

45
enter elements3

48
enter elements4

54
12

45

48

54

Process Exit...
*/

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.