 <p>The question is really, whether you need the CSR format immediately after the insertion, or you can rather have more insertions first in a more insertion friendly format and convert then to CSR.</p> <p>You may have a look at <a href="http://www-users.cs.umn.edu/~saad/software/SPARSKIT/" rel="nofollow">sparskit</a> and its linked list storage format, or you may create yourself some linked list for the new elements, and once you finished insertion, you could build up a new CSR formatted matrix, sparing a lot of reshuffling the data.</p>