Размер подмассива в сортировке слиянием

Question

У меня проблемы с пониманием размеров подмассивов в сортировке слиянием.В следующем коде:

   public void mergeSort(List<Integer> list, int low, int high){

       if(low<high){
           int mid = (high+low)/2;
           mergeSort(list,low, mid);
           mergeSort(list,mid+1,high);
           merge(list, low, mid, high);

       }
   }

   private void merge(List<Integer> list ,int low, int mid, int high){

       int lSize = mid-low+1;
       int rSize = high-mid;
   //etc 
   }

Для размера подмассивов я должен добавить 1 слева, в то время как правый массив не добавляет 1. Я понимаю, что если бы у нас был массив размером 10, индексы будут 0,9, а lSize будет 4-0 + 1, а rSize будет 9-4.

Я не совсем уверен, как это выразить, но у меня возникают проблемы с тем, чтобы обернуть голову, где добавить +1, не выполняя целый примерный массив размером 10 в моей голове.Если я не касаюсь mergesort некоторое время, я забываю, где добавить +1.Есть ли более простой способ запомнить это?Спасибо.

Answer 1

Ошибка переполнения

Во-первых, вы никогда не должны добавлять, а затем делить индексы.Если массив очень большой и вы находитесь ближе к концу массива, индексы low и high могут суммироваться в отрицательное число, если они переполняются Integer.MAX_VALUE.Затем, разделив это на два, получим отрицательное значение вместо ожидаемого положительного значения.

Вот сообщение в блоге Google о проблеме .Исправленный способ в Java (обратите внимание, что это >>>, а не >>):

int mid = (high + low) >>> 1;

Рассуждение

С учетом сказанного, вот сложный способ выяснить это, а затемпростой способ понять это.

Проблема заключается в том, как обрабатывать четное или нечетное значение low и четное или нечетное значение high, чтобы левая и правая стороны всегда были достаточно сбалансированы по размеру.

Давайте создадим таблицу с допустимыми значениями lSize и rSize, которые сбалансированы должным образом:

┏━━━━┯━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ low ╲ high ┃     4      ┃     5      ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━╇━━━━━━━━━━━━┫
┃     0      ┃ 2/3 or 3/2 │    3/3     ┃
┣━━━━━━━━━━━━╉────────────┼────────────┨
┃     1      ┃    2/2     │ 2/3 or 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━┷━━━━━━━━━━━━┛

* * * * * * * * * * * * * * *

*1031** Итак, мы знаем, что это будет что-то вроде mid - low и high - mid, но нам, возможно, придется настроить его.Суммируют ли они общий размер, с которым вы работаете?

┏━━━━┯━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┓
┃ low ╲ high ┃           4           ┃           5           ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━┫
┃     0      ┃ (2 - 0) + (4 - 2) = 4 │ (2 - 0) + (5 - 2) = 5 ┃
┣━━━━━━━━━━━━╉───────────────────────┼───────────────────────┨
┃     1      ┃ (2 - 1) + (4 - 2) = 3 │ (3 - 1) + (5 - 3) = 4 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━┛

Итак, мы на единицу меньше, чем должны быть, поэтому нам нужно добавить один к mid - low или high - mid, но какой?Итак, мы создаем таблицы для обоих и сравниваем с нашей первой таблицей.

Что произойдет, если мы добавим одну к mid - low?

┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃  4  ┃  5  ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃     0      ┃ 3/2 │ 3/3 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃     1      ┃ 2/2 │ 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛

Как видите, это соответствует приемлемомуварианты в нашей самой первой таблице.Что произойдет, если мы добавим один к high - mid?

┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃  4  ┃  5  ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃     0      ┃ 2/3 │ 2/4 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃     1      ┃ 1/3 │ 2/3 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛

Как видите, это не сбалансировано.

Итак, у нас есть mid - low + 1 и high - mid.

Простой способ выяснить это

При отладке выведите значения lSize и rSize (System.err.printf("L:%d R:%d\n", lSize, rSize);) с добавленным к lSize, а затем с добавленным к rSize.Попробуйте с различными размерами массива и посмотрите, какой баланс левой и правой сторон лучше всего.

Answer 2

Вот пример.Скажем, в списке 10 элементов.Вот индексы в списке

0 1 2 3 4 5 6 7 8 9

Теперь список нужно разбить пополам и каждую половину отсортировать рекурсивно - 0 1 2 3 4в одной половине 5 6 7 8 9 в другой.Таким образом, первая половина должна останавливаться на 4, а вторая половина должна начинаться на 5 и заканчиваться на 9.

Если вы вычисляете половину путевой точки mid = (9 + 0) / 2, это должно быть 4,5, но так как этоцелочисленная математика, она усекается (не округляется, усекается ) до 4. Таким образом, вы используете mid (4) в качестве конца первой половины и mid + 1 (5) в качестве началавторая половина.

Надеюсь, это прояснит ситуацию.