memmove vs. copying individual array elements

Question

In CLRS chapter 2 there is an exercise which asks whether the worst-case running time of insertion sort be improved to O(n lg n). I saw this question and found that it cannot be done.

The worst-case complexity cannot be improved but would by using memmove the real running time be better compared to individually moving the array elements?

Code for individually moving elements

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

Code for moving elements by using memmove

void insertion_sort(int arr[], int length)
{
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
                ;
        }
        if (k != j - 1){
            memmove(&arr[k + 2], &arr[k + 1], sizeof(int) *(j - k - 2));
        }
        arr[k + 1] = temp;
    }
}

I couldn't get the 2nd one to run perfectly but that is an example of what I am thinking of doing.

Would there be any visible speed improvements by using memmove?

Answer 1

It all depends on your compiler and other implementation details. It is true that memmove can be implemented in some tricky super-optimized way. But at the same time a smart compiler might be able to figure out what your per-element copying code is doing and optimize it in the same (or very similar) way. Try it and see for yourself.