Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

InsertionSort on sorted arrays

Name: Anonymous 2011-09-11 20:47

can anyone say at which point it is preferable to use InsertionSort instead of MergeSort.
I don't mean at array size but at how much of the array is already sorted

so anyone has any idea, 95%, 97%, 99% sorted?

Name: n3n7i 2011-09-11 22:56

Eg

1, 2, 4, 5, 7, 8, 10, 11, 12,(<<Sorted // new >>) 15, 13, 9, 14, 6,

Sort new data? (15, 13, 9, 14, 6 >> 6, 9, 13, 14, 15)

1, 2, 4, 5, 7, 8, 10, 11, 12,  6, 9, 13, 14, 15

n=2 (6, 9 < 12 // 13, 14, 15 > 12)

Add two entries?

1, 2, 4, 5, 7, 8, 10, 11, 12, 6, 9, 13, 14, 15, _, _,

Switch-out?

1, 2, 4, 5, 7, 8, [10, 11, 12,] _, _, 13, 14, 15, 6, 9

step 2 (12> x >9)

1, 2, 4, 5, (7, 8,) _, _, [10, 11, 12,] 13, 14, 15, 6, 9

step 1 (9> x >6)

1, 2, 4, 5, _, (7, 8,) _, 10, 11, 12, 13, 14, 15, 6, 9

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List