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

Question

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

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

int[] merge(int[] a , int[] b) 

Теперь моя сортировка слиянием рутина, как показано ниже

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

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

Answer 3

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

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

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

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 
}