Merge Sort Algorithm in Java

The merge sort algorithm is a divide and conquer algorithm that divides the array into two equal parts and applies merge sort on each half recursively. After the two parts are sorted, then both parts are merged again. The algorithm is illustrated in below figure:

Merge Sort illustration

The above illustration show merge sort of an array of eight elements (2 9 5 4 8 1 6 7). The original array is split into (2 9 5 4) and (8 1 6 7). Apply merge sort on these two subarrays recursively to split (1 9 5 4) into (1 9) and (5 4) and (8 1 6 7) into (8 1) and (6 7). This process continues until the subarray contains only one element. For example, array (2 9) is split into subarrays (2) and (9). Since array (2) contains a single element, it cannot be further split. Now merge (2) with (9) into a new sorted array (2 9); merge (5) with (4) into a new sorted array (4 5). Merge (2 9) with (4 5) into a new sorted array (2 4 5 9), and finally merge (2 4 5 9) with (1 6 7 8) into a new sorted array (1 2 4 5 6 7 8 9).

The merge sort algorithm is implemented in below code Listing.

MergeSort.java

public class MergeSort {

       public static void mergeSort(int[] list) {

              if (list.length > 1) {

                     // Merge sort the first half

                     int[] firstHalf = new int[list.length / 2];

                     System.arraycopy(list, 0, firstHalf, 0, list.length / 2);

                     mergeSort(firstHalf);

                     // Merge sort the second half

                     int secondHalfLength = list.length - list.length / 2;

                     int[] secondHalf = new int[secondHalfLength];

                     System.arraycopy(list, list.length / 2, secondHalf, 0,

                                  secondHalfLength);

                     mergeSort(secondHalf);

                     // Merge firstHalf with secondHalf

                     int[] temp = merge(firstHalf, secondHalf);

                     System.arraycopy(temp, 0, list, 0, temp.length);

              }

       }

       /** Merge two sorted lists */

       private static int[] merge(int[] list1, int[] list2) {

              int[] temp = new int[list1.length + list2.length];

              int current1 = 0; // Current index in list1

              int current2 = 0; // Current index in list2

              int current3 = 0; // Current index in temp

              while (current1 < list1.length && current2 < list2.length) {

                     if (list1[current1] < list2[current2]) {

                           temp[current3++] = list1[current1++];

                     } else {

                           temp[current3++] = list2[current2++];

                     }

              }

              while (current1 < list1.length) {

                     temp[current3++] = list1[current1++];

              }

              while (current2 < list2.length) {

                     temp[current3++] = list2[current2++];

              }

              return temp;

       }

       /** A test method */

       public static void main(String[] args) {

              int[] list = { 2, 9, 5, 4, 8, 1, 6, 7, };

              mergeSort(list);

              for (int i = 0; i < list.length; i++) {

                     System.out.print(list[i] + " ");

              }

       }

}

The output of this program is:

    1 2 4 5 6 7 8 9  


Reference(s): Introduction to JAVA by Y. Daniel Liang

Bubble Sort Algorithm in Java

The bubble sort algorithm makes several passes through the list. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise, the values remain unchanged. The technique is called a bubble sort, because the smaller values gradually “bubble” their way to the top and the larger values sink to the bottom. After first pass, the last element becomes the largest in the list. After the second pass, the second-to-last element becomes the second largest in the list. This process is continued until all elements are sorted.

Below figure shows Bubble Sort illustration with its various passes:

Bubble Sort illustration

Now the same iterations (algorithm) are discussed in below code Listing: 

BubbleSort.java

public class BubbleSort {

       /** Bubble sort method */

       public static void bubbleSort(int[] list) {

              boolean needNextPass = true;

              for (int k = 1; k < list.length && needNextPass; k++) {

                     // Array may be sorted and next pass not needed

                     needNextPass = false;

                     for (int i = 0; i < list.length - k; i++) {

                          if (list[i] > list[i + 1]) {

                               // Swap list[i] with list[i + 1]

                               int temp = list[i];

                               list[i] = list[i + 1];

                               list[i + 1] = temp;

                               needNextPass = true; // Next pass still needed

                          }

                     }

              }

       }

       public static void main(String[] args) {

              int[] list = { 2, 9, 5, 4, 8, 1 };

              bubbleSort(list);

              for (int i = 0; i < list.length; i++)

                     System.out.print(list[i] + " ");

       }

}

  The output of the program will be:

    1 2 4 5 8 9 


Reference(s): Introduction to JAVA by Y. Daniel Liang

How to find Greatest Common Divisor in Java

In this post I am going  to present an efficient algorithm for finding the greatest common divisor between two integers using recursion.

The greatest common divisor of two integers is the largest number that can properly divide both numbers. The program ask for two input parameter and then then calculate the greatest common divisor recursively.


GreatestCommonDivisor.java

import java.util.Scanner;

public class GreatestCommonDivisor {

       /** Find gcd for integers m and n */

       public static int gcd(int m, int n) {

              if (m % n == 0) {

                     return n;

              } else {

                     return gcd(n, m % n);

              }

       }

       /** Main method */

       public static void main(String[] args) {

              // Create a Scanner

              Scanner input = new Scanner(System.in);

              // Prompt the user to enter two integers

              System.out.print("Enter first integer: ");

              int m = input.nextInt();

              System.out.print("Enter second integer: ");

              int n = input.nextInt();

              System.out.println("The greatest common divisor for " + m + 

                        " and " + n + " is " + gcd(m, n));

       }

}

The output of the program should look like:

    Enter first integer: 525
   Enter second integer: 20
   The greatest common divisor for 525 and 20 is: >> 5