I am just looking at the inner workings of a Merge Sort algorithm which
tries to merge
t[lo .. mid by s] which is sorted
and
t[mid + 1 … hi by s] which is also sorted
back into itself, i.e. t[lo…hi by s] where s is the stride of ‘t’.
Could I get comments on my any comments below beginning with IS please?
proc mergeTwoBits
(
t: [?tDom] ?tType,
lo : ?I,
mid : I,
hi : I
)
{
// duplicate 't' but with a stride guaranteed to be one making
// its access during comparisons as cache friendly as possible
// IS this declaration and implicit copy the absolute optimal
// or should it be done with a 'forall' or done different ways
// depending on whether the stride is one (1) or not one (!= 1)?
const b : [lo..hi] tType = t;
// some integers to drive things
const s = tDom.stride;
var i = lo, j = mid + 1, k = lo;
// effectively split the copy as lower/upper chunks,
// i.e. b[lo .. mid] and b[mid+1 .. hi] respectively
//
// merge this split copy back into the original until
// one of those chunks is exhausted of elements
while i <= mid && j <= hi do
{
var _k : k.type;
if b[i] <= b[j] then
{
_k = i; i += 1;
}
else
{
_k = j; j += 1;
}
t[k] = b[_k];
k += s;
}
// copy any of the lower piece that is left
// IS if i <= mid then t[k .. hi by s] = b[i .. mid] any better/faster
// NOTE THAT if i <= mid then t[k..hi::s] = b[i..mid] looks cleaner
while i <= mid do
{
t[k] = b[i];
i += 1;
k += s;
}
// copy any of the upper piece that is left
// IS if j <= hi then t[k .. hi by s] = b[j .. hi] any better/faster
// NOTE THAT if i <= mid then t[k..hi::s] = b[j..hi] looks cleaner
while j <= hi do
{
t[k] = b[j];
j += 1;
k += s;
}
}
proc main
{
var x : [1..100] int;
// a whole lot of missing stuff goes in here
mergeTwoBits(x, 1, 50, 100);
}
Regards - Damian
Pacific Engineering Systems International, 277-279 Broadway, Glebe NSW 2037
Ph:+61-2-8571-0847 … Fx:+61-2-9692-9623 | unsolicited email not wanted here
Views & opinions here are mine and not those of any past or present employer