Return to Revisions

Reducing number of writes

Right now, you swap neighboring elements until the newest element reaches its proper place. This takes 2n array writes to move an element n spots. Instead of swapping, you can shift array elements up a position, and then write the newest element into its correct place. This takes n array writes, which cuts in half the number of writes you need to make.

Here is what the code would look like:

void insertion_sort(int arr[], int length)
{
 int i,j;
 for (i = 1; i < length; i++) {
 int tmp = arr[i];
 for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
 arr[j] = arr[j - 1];
 }
 arr[j] = tmp;
 }
}