Базовое условие в сортировке слиянием

Question

Я пытаюсь реализовать сортировку слиянием, и у меня возникают проблемы с реализацией базового условия.

У меня есть функция merge, которая принимает два отсортированных массива и возвращает объединенный массив.1005 *

Теперь моя процедура сортировки слиянием выглядит следующим образом

private static int[] mergeSort(int[] a, int low , int high)
{
    int mid = (low + high)  /2;
    if (low  < high)
    {
        return  merge( mergeSort(a,low, mid-1), mergeSort(a, mid , high));
    }
    return //return what ?
}

Какое базовое условие здесь?Какую ошибку я делаю?

Answer 1

Базовое условие - это когда у вас есть один элемент списка a, который по определению уже отсортирован.Просто верни его.

Answer 2

У метода сортировки есть два условия возврата:

• базовое условие - массив содержит только один элемент
• объединенное условие - два отсортированных массива были объединены

Метод слияния должен принимать два отсортированных массива и возвращать один отсортированный массив.

public int[] sort(int[] input){
  int mid = input.length/2;
  if(input.length > 1){
    // create and populate left and right arrays to merge
    // left  => input[0   > mid-1]
    // right => input[mid > input.length]
    return merge(sort(left), sort(right));
  }
  return input;
}

public int[] merge(int[] left, int[] right){
  // your merge logic
}

Answer 3

Просто верните a, поскольку оно уже отсортировано (оно содержит не более одного элемента).