何も見ないで書いてみた（マージソート）(2007/07/23(月) 23:57:46)

何も見ないでマージソートを書いてみた。
初め

int *tmp = new int[num];

で、マージするための領域用意したのに

if(j >= num || (i < left && array[i] < array[j]))array[k++] = array[i++]; 
else array[k++] = array[j++];

と書いていて、tmpのコピーも開放も忘れていた・・・。
必殺！！バグの嵐・・・

ソース

void mergeSort(int *array, int num){ 
  if(num == 1)return; 
  if(num == 2){ 
    if(array[0] > array[1]){ 
      int tmp = array[0]; 
      array[0] = array[1]; 
      array[1] = tmp; 
    } 
    return; 
  } 

  int left = num / 2; 
  int right = num - left; 

  mergeSort(array, left); 
  mergeSort(array + left, right); 

  int *tmp = new int[num]; 
  int i = 0, j = left, k = 0; 
  while(i < left || j < num){ 
    if(j >= num || (i < left && array[i] < array[j]))tmp[k++] = array[i++]; 
    else tmp[k++] = array[j++]; 
  } 
  memcpy(array, tmp, sizeof(int) * num); 
  delete tmp; 
}

参考

俺の頭の中