Merge Sort Algorithm

Problem Statement

Write a method named mergeSort that takes an unsorted integer array as input and returns a new sorted array in ascending order using the Merge Sort algorithm.

Function Signature

public static int[] mergeSort(int[] array)

• Input:
  • array: An unsorted integer array.
• Output:
  • A new sorted array containing all elements from the input array in ascending order.

 

---

🔹 Instructions

To implement mergeSort, you must use the merge method defined below.
This merge method merges two sorted arrays into one sorted array efficiently.

public static int[] merge(int[] array1, int[] array2) {
    int[] combined = new int[array1.length + array2.length];
    int index = 0;
    int i = 0;
    int j = 0;
    while (i < array1.length && j < array2.length) {
      if (array1[i] < array2[j]) {
        combined[index] = array1[i];
        index++;
        i++;
      } else {
        combined[index] = array2[j];
        index++;
        j++;
      }
    }
    while (i < array1.length) {
      combined[index] = array1[i];
      index++;
      i++;
    }
    while (j < array2.length) {
      combined[index] = array2[j];
      index++;
      j++;
    }
    return combined;
}

 

Example

Example 1

int[] array = {4, 2, 7, 1};
int[] result = mergeSort(array);
System.out.println(Arrays.toString(result));

Output:

[1, 2, 4, 7]

Example 2

int[] array = {10, 3, 15, 7, 8, 23, 74, 18};
int[] result = mergeSort(array);
System.out.println(Arrays.toString(result));

Output:

[3, 7, 8, 10, 15, 18, 23, 74]

Example 3

int[] array = {1};
int[] result = mergeSort(array);
System.out.println(Arrays.toString(result));

Output:

[1]

---

Constraints

1. The length of array is at least 1 (array.length ≥ 1).
2. The function must not modify the input array.
3. The function must use the merge sort algorithm, which has an average time complexity of O(N log N).
4. The method should return a new sorted array instead of sorting in place.

---

1. first approach

 

  public static int[] mergeSort(int[] array) {
    if (array.length == 1) {
      return array;
    }

    int middle = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, array.length);

    return merge(mergeSort(left), mergeSort(right));
  }