suppose I got these integers 6,1,4,2,1,5,9,6,3,4 and the size of run is 2 so we start by insertion sort of each run and i get these sub arrays:
1-6, 2-4, 1-5, 6-9, 3-4
my question is how do I merge them to get the sorted array?? I mean do I merge each two arrays and then the rest etc etc ?
Once you create the initial runs, you then merge the runs. Timsort uses a stack to keep track of run boundaries, and uses the top 3 entries on the stack to decide which runs to merge to "balance" the merges while maintaining "stability". A queue (FIFO) instead of a stack (LIFO) could be used (although I'm not sure if that would still be technically timsort) . With 10 elements, a run size of 3 would take one less merge pass. Timsort normally uses a larger minimum run size, 32 to 64 (inclusive), using insertion sort to force minimum run size if a natural run is smaller than it's calculated ideal minimum run size. Link to wiki article: