Что случилось с моей реализацией сортировки слиянием (C++)?

Question

Моя реализация сортировки слияния работает только частично и даже иногда увеличивает количество сбоев.

Входной сигнал: 5 4 3 2 1 Выход: 0 1 2 3 4

Входной сигнал: 7 6 5 4 3 2 1 Выход: 0 1 2 3 4 5 6

Входной сигнал: 4 3 2 1 Выход: [некоторый мусор значение] 1 2 3

Входной сигнал: 1 2 3 4 5 67 7 8 Выход: [некоторый мусор значение] 1 2 3 4 5 7 8

кажется, что входы с нечетным номером не вызывают seg-ошибки, но четные номера. Тем не менее, в обоих случаях наибольшее значение не появляется на выходе. Любая помощь будет оценена по достоинству.

void merge(vector<int>& a, int i, int j) 
{ 
    int b[a.size()]; 
    int start = i; 
    int mid = (i+j)/2; 
    int k = mid+1; 
    int l = i; 
    while(i<=mid && k<=j) 
    { 
     if(a[i] >= a[k]) 
     b[l++] = a[k++]; 
     else 
     b[l++] = a[i++]; 
    } 

    if(i>mid) 
    { 
     while(k<=j) 
     b[l++] = a[k++]; 
    } 
    else 
    { 
     while(i<=mid) 
     b[l++] = a[i++]; 
    } 

    for(l=start; l<=j; l++) 
     a[l] = b[l]; 
} 

void merge_sort(vector<int>& a, int l, int u) 
{ 
    int m; 
    if(l < u) 
    { 
      m = (l+u)/2; 
      merge_sort(a,l,m); 
      merge_sort(a,m+1,u); 
      merge(a,l,u); 
     } 
} 

//relevant portion in main 
    cin >> n; 
    cout << "n: " << n << endl; 
    a.resize(n); 
    for(int j=0; j<n; j++) 
    cin >> a[j]; 

    cout << endl; 
    merge_sort(a, 0, a.size()); 

Answer 1

Вы не должны идти до j ("...<= j..."), когда j может быть a.size(). Попробуйте a.size() - 1.