LeetCode Medium Challenge Day 23 | Sort an Array

PROBLEM LINK - CLICK

Problem Statement

Given an array of integers, the task is to sort the array in ascending order using the merge sort algorithm. Merge sort is a divide-and-conquer algorithm that recursively splits the array into smaller subarrays, sorts them, and then merges them back together to produce a sorted array.

Explanation of the Code

The Solution class contains a method sortArray that takes an integer array as input and returns the sorted array using the merge sort algorithm. The core of the sorting logic is implemented in two methods: mergeSort and recursiveSort.

Step 1: The sortArray Method

The sortArray method is the entry point for sorting. It takes an array nums as input and calls the mergeSort method to sort it.

public int[] sortArray(int[] nums) {
    int[] result = mergeSort(nums);
    return result;
}        

Step 2: The mergeSort Method

The mergeSort method is responsible for initializing the sorting process. It takes the input array arr, and calls the recursiveSort method to perform the actual sorting. The mergeSort method doesn't need to create an extra result array, as the sorting happens in-place.

public static int[] mergeSort(int[] arr) {
    return recursiveSort(arr);
}        

Step 3: The recursiveSort Method

The recursiveSort method is where the divide-and-conquer strategy is applied. This method:

1. Base Case: If the array has one or zero elements, it is already sorted, so the method returns the array immediately.
2. Divide: The array is split into two halves, left and right.
3. Recursive Calls: The method recursively sorts both the left and right halves.
4. Merge: The sorted left and right arrays are merged into a single sorted array

private static int[] recursiveSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    int mid = arr.length / 2;

    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);

    left = recursiveSort(left);
    right = recursiveSort(right);

    return merge(left, right);
}        

Step 4: The merge Method

The merging process combines the two sorted arrays (left and right) into a single sorted array. It compares the elements of both arrays and places the smaller element into the main array arr. If one array is exhausted before the other, the remaining elements of the non-exhausted array are copied directly into arr.

private static int[] merge(int[] left, int[] right) {
    int[] arr = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    while (i < left.length) {
        arr[k++] = left[i++];
    }

    while (j < right.length) {
        arr[k++] = right[j++];
    }

    return arr;
}