Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Merge Sort for Object Sorting

Problem Statement

Write a Java program that extends the Merge Sort implementation to sort an array of objects, specifically Student objects with a grade field, in ascending order based on a custom comparator that compares grades. The program should test the implementation with a sample dataset containing Student objects with varied grades, including duplicates and edge cases like empty arrays, verifying that the output is correctly sorted. Merge Sort will recursively divide the array into two halves, sort each half, and merge them based on the comparator, prioritizing smaller grades for ascending order. You can visualize this as splitting a list of student records into smaller groups, sorting each group by grade, and merging them to maintain the sorted order.

Input:

  • An array of Student objects, each with a name (String) and grade (double) field. Output: The sorted array (by grade in ascending order) and a string representation of the input and sorted arrays for verification. Constraints:
  • The array length n is between 0 and 10^5.
  • Grades are doubles in the range [0.0, 100.0]. Example:
  • Input: array = [Student("Alice", 85.5), Student("Bob", 92.0), Student("Charlie", 78.5)]
  • Output:
    • Input Array: [Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0), Student(name=Charlie, grade=78.5)]
    • Sorted Array: [Student(name=Charlie, grade=78.5), Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0)]
  • Explanation: Merge Sort divides, sorts, and merges to produce an ascending order array by grade.
  • Input: array = [Student("Eve", 90.0), Student("Eve", 90.0)]
  • Output:
    • Input Array: [Student(name=Eve, grade=90.0), Student(name=Eve, grade=90.0)]
    • Sorted Array: [Student(name=Eve, grade=90.0), Student(name=Eve, grade=90.0)]
  • Explanation: Duplicate grades are preserved in order due to Merge Sort’s stability.

Pseudocode

FUNCTION mergeSort(arr, left, right, comparator)
    IF left < right THEN
        SET mid to floor((left + right) / 2)
        CALL mergeSort(arr, left, mid, comparator)
        CALL mergeSort(arr, mid + 1, right, comparator)
        CALL merge(arr, left, mid, right, comparator)
    ENDIF
ENDFUNCTION

FUNCTION merge(arr, left, mid, right, comparator)
    SET n1 to mid - left + 1
    SET n2 to right - mid
    CREATE leftArr as array of size n1
    CREATE rightArr as array of size n2
    FOR i from 0 to n1-1
        SET leftArr[i] to arr[left + i]
    ENDFOR
    FOR i from 0 to n2-1
        SET rightArr[i] to arr[mid + 1 + i]
    ENDFOR
    SET i to 0, j to 0, k to left
    WHILE i < n1 AND j < n2
        IF comparator.compare(leftArr[i], rightArr[j]) <= 0 THEN
            SET arr[k] to leftArr[i]
            INCREMENT i
        ELSE
            SET arr[k] to rightArr[j]
            INCREMENT j
        ENDIF
        INCREMENT k
    ENDWHILE
    WHILE i < n1
        SET arr[k] to leftArr[i]
        INCREMENT i
        INCREMENT k
    ENDWHILE
    WHILE j < n2
        SET arr[k] to rightArr[j]
        INCREMENT j
        INCREMENT k
    ENDWHILE
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element.toString() to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of Student arrays
    SET gradeComparator to new Comparator comparing Student grades
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        CALL mergeSort(copy, 0, length-1, gradeComparator)
        PRINT input array, sorted array
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define Student class: a. Fields: name (String), grade (double). b. Include toString for readable output.
  2. Define mergeSort (generic): a. Accept an array of type T, left, right indices, and a Comparator<T>. b. If left < right, divide array at mid, recursively sort halves, and merge using merge.
  3. Define merge (generic): a. Create temporary arrays for left and right halves. b. Use comparator to merge elements in ascending order (comparator.compare(leftArr[i], rightArr[j]) <= 0). c. Copy remaining elements from either half.
  4. Define toString: a. Convert array to a string, e.g., "[Student(name=Alice, grade=85.5), ...]".
  5. In main, test with: a. Mixed grades (n=5). b. Duplicate grades (n=4). c. Empty array (n=0). d. Single-element array (n=1). e. Sorted grades (n=6).

Java Implementation

import java.util.*;

public class MergeSortObjectSorting {
    // Student class
    static class Student {
        String name;
        double grade;

        Student(String name, double grade) {
            this.name = name;
            this.grade = grade;
        }

        @Override
        public String toString() {
            return "Student(name=" + name + ", grade=" + grade + ")";
        }
    }

    // Performs Merge Sort with custom comparator
    public <T> void mergeSort(T[] arr, int left, int right, Comparator<T> comparator) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, comparator);
            mergeSort(arr, mid + 1, right, comparator);
            merge(arr, left, mid, right, comparator);
        }
    }

    // Merges two sorted subarrays using comparator
    private <T> void merge(T[] arr, int left, int mid, int right, Comparator<T> comparator) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        @SuppressWarnings("unchecked")
        T[] leftArr = (T[]) new Object[n1];
        @SuppressWarnings("unchecked")
        T[] rightArr = (T[]) new Object[n2];

        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        // Merge in ascending order
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (comparator.compare(leftArr[i], rightArr[j]) <= 0) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    // Converts array to string
    public <T> String toString(T[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i].toString());
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Student[] arr;
        String description;

        TestCase(Student[] arr, String description) {
            this.arr = arr;
            this.description = description;
        }
    }

    // Main method to test object sorting
    public static void main(String[] args) {
        MergeSortObjectSorting sorter = new MergeSortObjectSorting();

        // Comparator for sorting by grade
        Comparator<Student> gradeComparator = (s1, s2) -> Double.compare(s1.grade, s2.grade);

        // Test cases
        TestCase[] testCases = {
            new TestCase(new Student[]{
                new Student("Alice", 85.5),
                new Student("Bob", 92.0),
                new Student("Charlie", 78.5),
                new Student("David", 95.0),
                new Student("Eve", 88.0)
            }, "Mixed grades (n=5)"),
            new TestCase(new Student[]{
                new Student("Frank", 90.0),
                new Student("Grace", 90.0),
                new Student("Hannah", 90.0),
                new Student("Ivy", 90.0)
            }, "Duplicate grades (n=4)"),
            new TestCase(new Student[]{}, "Empty (n=0)"),
            new TestCase(new Student[]{new Student("Jack", 75.0)}, "Single element (n=1)"),
            new TestCase(new Student[]{
                new Student("Kate", 70.0),
                new Student("Liam", 75.0),
                new Student("Mia", 80.0),
                new Student("Noah", 85.0),
                new Student("Olivia", 90.0),
                new Student("Peter", 95.0)
            }, "Sorted grades (n=6)")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            Student[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            sorter.mergeSort(arr, 0, arr.length - 1, gradeComparator);
            System.out.println("Sorted Array: " + sorter.toString(arr) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Mixed grades (n=5)
Input Array: [Student(name=Alice, grade=85.5), Student(name=Bob, grade=92.0), Student(name=Charlie, grade=78.5), Student(name=David, grade=95.0), Student(name=Eve, grade=88.0)]
Sorted Array: [Student(name=Charlie, grade=78.5), Student(name=Alice, grade=85.5), Student(name=Eve, grade=88.0), Student(name=Bob, grade=92.0), Student(name=David, grade=95.0)]

Test case 2: Duplicate grades (n=4)
Input Array: [Student(name=Frank, grade=90.0), Student(name=Grace, grade=90.0), Student(name=Hannah, grade=90.0), Student(name=Ivy, grade=90.0)]
Sorted Array: [Student(name=Frank, grade=90.0), Student(name=Grace, grade=90.0), Student(name=Hannah, grade=90.0), Student(name=Ivy, grade=90.0)]

Test case 3: Empty (n=0)
Input Array: []
Sorted Array: []

Test case 4: Single element (n=1)
Input Array: [Student(name=Jack, grade=75.0)]
Sorted Array: [Student(name=Jack, grade=75.0)]

Test case 5: Sorted grades (n=6)
Input Array: [Student(name=Kate, grade=70.0), Student(name=Liam, grade=75.0), Student(name=Mia, grade=80.0), Student(name=Noah, grade=85.0), Student(name=Olivia, grade=90.0), Student(name=Peter, grade=95.0)]
Sorted Array: [Student(name=Kate, grade=70.0), Student(name=Liam, grade=75.0), Student(name=Mia, grade=80.0), Student(name=Noah, grade=85.0), Student(name=Olivia, grade=90.0), Student(name=Peter, grade=95.0)]

Explanation:

  • Test case 1: Mixed grades (n=5) are sorted by grade in ascending order.
  • Test case 2: Duplicate grades (n=4, all 90.0) are sorted, preserving order due to stability.
  • Test case 3: Empty array (n=0) remains empty.
  • Test case 4: Single-element array (n=1) is trivially sorted.
  • Test case 5: Already sorted by grade (n=6) remains unchanged.

How It Works

  • Student Class:
    • Contains name (String) and grade (double).
    • Includes toString for readable output.
  • mergeSort:
    • Uses generics with Comparator<T> to sort any object type.
    • Recursively divides the array and merges using the comparator.
  • merge:
    • Creates temporary arrays for left and right halves.
    • Merges elements based on comparator (comparator.compare(leftArr[i], rightArr[j]) <= 0), ensuring stability.
    • Copies remaining elements.
  • toString: Formats array as a string, handling Student objects.
  • Example Trace (Test case 1):
    • Array: [Alice(85.5), Bob(92.0), Charlie(78.5), David(95.0), Eve(88.0)].
    • Divide: [Alice(85.5), Bob(92.0), Charlie(78.5)] and [David(95.0), Eve(88.0)].
    • Divide: [Alice(85.5)] and [Bob(92.0), Charlie(78.5)]; [David(95.0)] and [Eve(88.0)].
    • Merge: [Bob(92.0), Charlie(78.5)] → [Charlie(78.5), Bob(92.0)].
    • Merge: [Alice(85.5)], [Charlie(78.5), Bob(92.0)] → [Charlie(78.5), Alice(85.5), Bob(92.0)].
    • Merge: [David(95.0)], [Eve(88.0)] → [Eve(88.0), David(95.0)].
    • Merge: [Charlie(78.5), Alice(85.5), Bob(92.0)], [Eve(88.0), David(95.0)] → [Charlie(78.5), Alice(85.5), Eve(88.0), Bob(92.0), David(95.0)].
  • Main Method: Tests mixed grades, duplicates, empty, single-element, and sorted arrays using a grade comparator.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
mergeSortO(n log n)O(n)
mergeO(n)O(n)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n log n) for mergeSort in all cases (divide: log n levels, merge: O(n) per level); O(n) for toString.
  • Space complexity: O(n) for mergeSort (temporary arrays); O(n) for toString (string builder).
  • Comparator comparisons depend on the field (e.g., double for grades), but complexity remains O(n log n).

✅ Tip: Use a Comparator to make Merge Sort flexible for sorting objects by any field. Ensure stability by using <= in the merge step to preserve the order of equal elements.

⚠ Warning: Ensure the comparator is consistent to avoid sorting errors. Use @SuppressWarnings("unchecked") for generic array creation in Java, and clone input arrays to preserve the original order for display.