Фирма "1С". "Алгоритмы. Олимпиадное программирование на языке Java для школьников"

Сортировка слиянием

Дополнительный массив на уровне класса.

static int[] tmpArray = new int[100000]; //100000 -  из ограничений

Функция слияния

static void merge( int [] a, 
                   int leftPos, int rightPos, int rightEnd ) 
{ 
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;
 
    while(leftPos <= leftEnd && rightPos <= rightEnd)
    if( a[leftPos] <= a[rightPos])
       tmpArray[tmpPos++] = a[leftPos++];
    else
       tmpArray[tmpPos++] = a[rightPos++];

    //копируем оставшиеся части
    while(leftPos <= leftEnd)     
    	tmpArray[tmpPos++] = a[leftPos++];

    while(rightPos <= rightEnd)   
    	tmpArray[tmpPos++] = a[rightPos++];

    // Копируем tmpArray обратно
    for(int i = 0; i < numElements; i++)
    {
        a[rightEnd] = tmpArray[rightEnd];
        rightEnd--; 
    }
}

Сама функция сортировки

static void mergeSort(int [] a, int left, int right) 
{
     if(left < right) 
     {
        int center = (left + right) / 2;
        mergeSort(a, left, center);
        mergeSort(a, center + 1, right);
        merge(a, left, center + 1, right);
     }
}