We have a very large stream, which size is N. This stream is almost sorted, but there are k elements disorder the array. k is far smaller than N. Find a way to sort this stream faster than O(NlogN)

Requirements:

You could define the struct of the stream.
N >> k eg: N is 1 million and k is 10
Time complecity should be strictly smaller than O(NlogN)

example input: N = [1,2,3,7,8,9,10,12,5,6,7]

It was left to my choice to pick data type of input stream and I picked list. Inteviewer then recommend a linkedlist.
Approach:
parse through list and every disordered set is a pair of elements. in aforementioned example 9,10,12,5,6,7 would fall in a disordered list and 1-> 7 is ordered.
Sorting multiple of K disordered list would take KlogK. At the end traverse both lists (sort of merge sort) and return the head

I think I bombed this but a good learning.
Hope this helps someone here.