Is insertion sort a stable algorithm?
What would make an algorithm unstable? If possible could you include examples?
--
If you haven't seen the new Community Initiative, click the link to learn more about EddiEE!
To ensure that the sort algorithm is stable, you must preserve the order of elements with the same keys. The insertion sorts works with the sorted part and unsorted part. You insert the element to the sorted part. To do that, you have to move portion of the sorted part to make the space for the inserted element. That means that you have to find the position and move the rest.
Usual implementation of the insertion sort combines searching for the position with moving of the rest of the sorted portion. You get and remember the first item from the unsorted part, and its current location will be used as empty space for moving the back element of the sorted portion. This way the space moves by one to the lower index. Once you find smaller or equal element, you store the remembered item to the empty slot. This way, the element with the same key will be placed after the previous elements with the same key. Their order will be preserved. This means that the sort is stable.
Anyway, if you stop searching only on smaller elements (you move the elements with the same key), you would make even the insertion sort both less efficient (unnecessary moves) and unstable. But that would be considered a flaw in implementation.
Regarding sorts, a stable algorithm is one where duplicated keys appear in the result set in the same order that the occurred in the original list.
Bob Jones
Amy Grant
Bob Ingram
Sorting by first name, the results could be
Amy Grant
Bob Ingram
Bob Jones
or
Amy Grant
Bob Jones
Bob Ingram
The second result would be considered stable because the two "Bob" rows appear in the same order that they did in the original list.