When it is said that this sort has M number of comparisons what does it mean?
As an example:
procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure
for i = 1 to n-1
for(int i = 0 ; i < n-1; i++)
is this comparison (
i < n-1) taken into account?
Or in merge sort, beside the main comparison:
at the end of a used function it is written:
while (first1 <= last1) temp[index++] = v[first1++]; while (first2 <= last2) temp[index++] = v[first2++]; for (index = first; index <= last; index++) v[index] = temp[index];
Are these comparisons are taken into account?