сравнение с использованием сортировки слияния и выбора сортировки

Question

У меня есть массив из 10 int и с использованием сортировки выбора. Я вычисляю, что для сортировки всего массива требуется около 45 сравнений, но я не уверен, сколько нужно сортировать по методу слияния по моим расчетам, требуется 12 сравнений .... я прав или не прав здесь?

Заранее спасибо

вот метод слияния

static void merge(int[] first, int[] second, int[] a) 
    { 
     int iFirst = 0; 
     int iSecond = 0; 
     int i = 0; 
     //moving the smaller element into a 
     while(iFirst < first.length && iSecond < second.length) 
     { 
      if(first[iFirst] < second[iSecond]) 
      { 
       a[i] = first[iFirst]; 
       iFirst++; 
      } 
      else 
      { 
       a[i] = second[iSecond]; 
       iSecond++; 
      } 
      i++;    
     } 
     counter += i; 

     //copying the remaning of the first array 
     while(iFirst < first.length) 
     { 
      a[i] = first[iFirst]; 
      iFirst++; i++; 
     } 
     //copying the remaining of second array 
     while(iSecond < second.length) 
     { 
      a[i] = second[iSecond]; 
      iSecond++; i++; 
     }   
    } 

Answer 1

Слить в n -элементного массива с m элементного массива, вам необходимы n+m-1 сравнений в худшем случае (min{m,n} в лучшем случае) ,

Поэтому, когда вы разбиваете массив из 10 элементов пополам, слияние верхнего уровня требует до 9 сравнений. Для двух пятиэлементных половин требуется до 4 сравнений, 9 + 2*4 = 17. Разделение пятиэлементных половин в 2-элементной и трехэлементной части требует до 1 + 3 сравнений, поэтому общим худшим случаем будет 25 сравнений (9 + 2 * 4 + 2 * 3 + 2 * 1).

   10(9)        9 
      / \ 
      /  \ 
      /  \ 
      /   \ 
     /   \ 
     /    \ 
     /    \ 
     5(4)    5(4)     8 
    / \   / \ 
    / \   / \ 
    3(2)  2(1)  3(2)  2(1)    6 
/ \ / \ / \ / \ 
    2(1) 1 1  1 2(1) 1 1  1    2 
/ \   / \ 
1  1   1  1