Insertion sort iterates through a dataset, partially sorting it as it goes along. When it finds a node that is in the wrong order relative to the value before it, it pulls out that node and inserts it in properly sorted order in the partially sorted section. As it keeps the values that have already been processed towards the head end of the array, it can be used for data that is streamed in while it is still being processed. Insertion sort performs more efficiently than the above methods in small datasets, reaching O(n) performance, but it performs at O(n^2) on the average case and thus is impractical for large datasets.