How to sort an alphabetic array using merge sort in Java

Merge sort is a divide-and-conquer sorting algorithm that works by recursively dividing the input array into smaller halves, sorting them independently, and then merging them back together to produce a sorted array.

Basic steps of the merge sort algorithm

The basic steps of the merge sort algorithm are as follows:

  • Divide: The input array is divided into two halves until each half contains only one element or is empty.

  • Conquer: The smaller subarrays are recursively sorted using the merge sort algorithm.

  • Merge: The sorted subarrays are merged back together by comparing the elements from the left and right halves and placing them in the correct order in a new merged array.

  • Merge (contd.): The merging process continues until all elements from both halves are merged into a single sorted array.

The following illustration helps us understanding the process of merge sort algorithm with the help of a numerical array.

Divide array into half
1 of 7

Implementation on an alphabetic array

The merge sort algorithm can be implemented on an alphabetic array. In this case, the comparison operation is carried out by string comparison or comparing the unicode/ASCII value of the character.

The following code implements a merge sort algorithm on an alphabetic array.

The input is an array as follows:

Original Array: [banana, apple, cherry, date, grape]

After the implementation of the merge sort algorithm, the output should be as follows:

Sorted Array: [apple, banana, cherry, date, grape]

It is to be noted that the output array is sorted alphabetically.

import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        String[] arr = {"banana", "apple", "cherry", "date", "grape"};
        
        System.out.println("Original Array: " + Arrays.toString(arr));
        
        mergeSort(arr);
        
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
    public static void mergeSort(String[] arr) {
        if (arr.length <= 1) {
            return;
        }
        
        int mid = arr.length / 2;
        String[] leftHalf = Arrays.copyOfRange(arr, 0, mid);
        String[] rightHalf = Arrays.copyOfRange(arr, mid, arr.length);
        
        mergeSort(leftHalf);
        mergeSort(rightHalf);
        
        merge(arr, leftHalf, rightHalf);
    }
    public static void merge(String[] arr, String[] leftHalf, String[] rightHalf) {
        int leftIndex = 0;
        int rightIndex = 0;
        int arrIndex = 0;
        
        while (leftIndex < leftHalf.length && rightIndex < rightHalf.length) {
            if (leftHalf[leftIndex].compareTo(rightHalf[rightIndex]) <= 0) {
                arr[arrIndex] = leftHalf[leftIndex];
                leftIndex++;
            } else {
                arr[arrIndex] = rightHalf[rightIndex];
                rightIndex++;
            }
            arrIndex++;
        }
        
        while (leftIndex < leftHalf.length) {
            arr[arrIndex] = leftHalf[leftIndex];
            leftIndex++;
            arrIndex++;
        }
        
        while (rightIndex < rightHalf.length) {
            arr[arrIndex] = rightHalf[rightIndex];
            rightIndex++;
            arrIndex++;
        }
    }
}

Explanation

  • Line 3: The line public class MergeSort is the declaration of a Java class named MergeSort.
  • Lines 6–12: In these lines of code, an array of strings arr is initialized with some values. The original array is printed using System.out.println() and Arrays.toString(). Then, the mergeSort() function is called to sort the array. Finally, the sorted array is printed again.
  • Lines 20–22: These lines divide the given array into two arrays. The left half of the array is stored in leftHalf and the right one in rightHalf.
  • Lines 24–25: This is a recursive call that keeps on dividing the subarrays further until only one element is left in the array.
  • Lines 35–44: The while loop continues as long as there are elements remaining in both the left and right halves of the array. It compares the elements at the current indexes of the left and right halves, assigns the smaller element to the arr array, and increments the corresponding index. The arrIndex is also incremented after each assignment.
  • Lines 46–56: The first while loop copies any remaining elements from the left half of the array to the arr array, incrementing the leftIndex, arrIndex, and continuing until all elements in the left half are processed. The second while loop copies any remaining elements from the right half of the array to the arr array, incrementing the rightIndex, arrIndex, and continuing until all elements in the right half are processed.

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)