有一種簡單的排序算法，叫做計數(shù)排序（count Sorting）。這種排序算法對一個待排序的表（用數(shù)組表示）進行排序，并將排序結果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對某一個記錄，統(tǒng)計出的計數(shù)值為 c，那么，這個記錄在新的有序表中的合適的存放位置即為 c。
（1）給出適用于計數(shù)排序的數(shù)據(jù)表定義；
（2）使用C++語言編寫實現(xiàn)計數(shù)排序的算法。

下面的程序是一個的兩路歸并算法merge，只需要一個附加存儲。設算法中參加歸并的兩個歸并段是A[left]～A[mid]和A[mid]～A[right]，歸并后結果歸并段放在原地。

若A = { 12， 28， 35， 42， 67， 9， 31， 70 }， left = 0， mid = 4， right = 7。寫出每次執(zhí)行算法最外層循環(huán)后數(shù)組的變化，并給出每次執(zhí)行算法最外層循環(huán)時的數(shù)據(jù)記錄移動次數(shù)。