You should use realloc() not each of i=..n iterations but rather for each log(n) - by doubling the size of the allocated array, rather than just increasing the size by one element.