Оптимальная сортировка для средних массивов

uint mth(uint* arr, uint a, uint b)
{
  uint size = b - a + 1; //вычисляем размер
  uint *temp = new uint[size]; //выделяем память
    
  for(int i = a - 1, i_temp = 0; i < b; i++, i_temp++)
    temp[i_temp] = arr[i]; //копируем нужный участок (std::copy ругается на небезопасное копирование, потому вот-так)
 
  sort(temp, temp + size);  //сортируем std::sort'ом 
 
  if(temp[0] != 0) return 0; //если нет нуля, то возвращаем его. Возможно будет быстрей сначала пройти весь 
                                        //кусок данного массива (arr) и узнать есть ли там ноль
 
  for(int i = 1; i < size; i++) //ищем прерывания 
    if(temp[i] - temp[i - 1] > 1)
    {
      size = temp[i - 1] + 1; //в size пихаем число
      delete[] temp; //очищаем память 
      return size; //возвращаем найденное число
    }
  
  //иначе, возвращаем максимальное
  size = temp[size - 1] + 1;
  delete[] temp;
  return size;
}

unsigned long find(const unsigned long*input,unsigned long N)
{
    const std::size_t maxN=1<<19;//чтоб не тратиться на динамическую память
    const std::size_t bitMaskSize=std::numeric_limits<unsigned long>::digits;
    const std::size_t maskArraySize=maxN/bitMaskSize;
    unsigned long maskArray[maskArraySize]={0};
    assert(N<=maxN);
 
    for(std::size_t i=0;i<N;++i)
    {
        const std::size_t maskIndex=input[i]/bitMaskSize;
        const unsigned bitNumber=input[i]%bitMaskSize;
        maskArray[maskIndex]|=1L<<bitNumber;
    }
    for(std::size_t i=0;i<maskArraySize;++i)
    {
        const unsigned long mask=maskArray[i];
        if(mask!=(unsigned long)(~0))
        {
            for(std::size_t offset=0;offset<bitMaskSize;++offset)
                if(!(mask&(1<<offset)))
                    return i*bitMaskSize+offset;
        }
    }
    return-1;
}

const std::size_t maxN=1<<19;
std::size_t countLevel0[maxN]={0};
std::size_t countLevel1[maxN/1024]={0};
 
//это дергать для чтения очередного значения массива
void insertValue(std::size_t value)
{
    if(!countLevel0[value]++)
        ++countLevel1[value/1024];
}
 
//для операции изменения элемента массива сначала пнуть removeValue, потом insertValue
void removeValue(std::size_t value)
{
    if(!--countLevel0[value])
        --countLevel1[value/1024];
}
 
std::size_t find(std::size_t minValue,std::size_t maxValue)
{
    const std::size_t min1=minValue/1024,max1=(maxValue+1023)/1024;
    for(std::size_t pos1=min1;pos1<max1;++pos1)
        if(countLevel1[pos1]<1024)
        {
            const std::size_t min0=std::max(minValue,min1*1024);
            const std::size_t max0=std::min(maxValue,(min1+1)*1024);
            for(std::size_t pos0=min0;pos0<max0;++pos0)
                if(!countLevel0[pos0])
                    return pos0;
        }
    return -1;
}

#include <iostream>
#include <vector>
#include <set>
 
 
using t_positions = std::set<unsigned>;
 
std::vector<t_positions> prepare(const std::vector<unsigned> & base)
{
    std::vector<t_positions> res(base.size());
    for(size_t i = 0; i<base.size(); ++i)
        res[base[i]].insert(i);
    return res;
}
 
 
void replace(size_t pos, unsigned value, std::vector<unsigned>& arr, std::vector<t_positions>& mapper)
{
    unsigned old = arr[pos];
    arr[pos] = value;
    
    mapper[old].erase(pos);
    mapper[value].insert(pos);
}
/// Both inclusive
bool is_set_contains(const t_positions& positions, size_t left, size_t right)
{
    if(positions.size()==0)
        return false;
    auto iter = positions.lower_bound(left);
    if(iter==positions.end() || *iter>right)
        return false;
    return true;
}
 
size_t first_lost(size_t left, size_t right, const std::vector<t_positions>& mapper)
{
    for(size_t i = 0; i<mapper.size(); ++i)
        if(!is_set_contains(mapper[i], left, right))
            return i;
    return mapper.size();
}
 
int main()
{
    size_t n;
    std::cin>>n;
    std::vector<unsigned> arr(n);
    for(unsigned &v:arr)
        std::cin>>v;
    std::vector<t_positions> mapper = prepare(arr);
    size_t number_of_commands;
    std::cin>>number_of_commands;
    for(size_t i = 0; i<number_of_commands; ++i)
    {
        char cmd;
        std::cin>>cmd;
        if(cmd=='?')
        {
            size_t l,r;
            std::cin>>l>>r;
            std::cout<<first_lost(l, r, mapper);
        }
        else
        {
            unsigned value;
            size_t pos;
            std::cin>>pos>>value;
            replace(pos, value, arr, mapper);
        }
    }
}