3 マージソート

3.1 手順

ここは教科書を使って説明する．

3.2 プログラムテクニック

• x[k++]=buffer[i++];

  これは，後値型のインクリメント演算子を用いており，

  	x[k]=buffer[i];
  	i++;
  	k++;
  

  
  とおなじである．反対に，前値型のインクリメント演算子を用いると， x[++k]=buffer[++i];は，

  	i++;
  	k++;
  	x[k]=buffer[i];
  

  
  と同一の働きとなる．

• 引数で配列名を渡すところに，x+mとなっている

  配列名は，配列の先頭を示すポインターである．したがって，配列名xに整 数mを加算するということは，ポインターをmだけ移動させたことにな る．したがって，x+mはx[m]を表すポインターとなっている．

3.3 ソートの様子

実際にソートした結果を示す．

ソート準備:
879 269 649 711 435 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531

ソート開始:
269 879 649 711 435 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 879 649 435 711 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 879 435 649 711 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531
269 435 649 711 879 311 701 303 605 879 857 419 298 278 817 713 983 469 832 531
269 435 649 711 879 303 311 605 701 879 857 419 298 278 817 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 857 419 298 278 817 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 419 857 298 278 817 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 419 857 298 278 817 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 419 857 278 298 817 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 832 531
269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 531 832
269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 531 832
269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 469 531 713 832 983
269 303 311 435 605 649 701 711 879 879 278 298 419 469 531 713 817 832 857 983
269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983

ソート終了:
269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983

ホームページ: Yamamoto's laboratory
著者: 山本昌志