[Verse 1]
Array scattered like a deck of cards thrown wild
Numbers out of sequence, chaos unreciled
Start with second element, call it the key
Compare it backwards, where should it be?
Shift every bigger value one spot to the right
Making space for insertion, positioning tight
Drop the key in its home, first pass complete
One more element sorted, algorithm neat
[Chorus]
Insert and shift, insert and shift
Key moves backward through the drift
Sorted portion grows each round
Insert and shift, that's the sound
In-place sorting, stable too
Insert and shift will see you through
[Verse 2]
Pick the third element, hold it in your grip
Slide it past the giants on its leftward trip
Best case scenario when data's pre-arranged
O of n complexity, efficiency unchanged
Worst case hits when everything's reversed
O of n squared, performance gets cursed
But insertion sort excels with small arrays
Adaptive nature always pays
[Chorus]
Insert and shift, insert and shift
Key moves backward through the drift
Sorted portion grows each round
Insert and shift, that's the sound
In-place sorting, stable too
Insert and shift will see you through
[Bridge]
Binary insertion cuts the comparisons down
Searching sorted portion, location gets found
But shifting elements still takes its toll
Time complexity keeps the same control
Stable algorithm maintains order's face
Equal elements keep their original place
[Verse 3]
Nearly sorted datasets make insertion shine
Linear performance, almost divine
Online algorithm processes streams
Sorting as data arrives, fulfilling dreams
Memory footprint stays constant and lean
Most efficient small-scale sorting machine
[Outro]
From left to right the boundary expands
Sorted region grows beneath your hands
Insert and shift, the ancient dance
Giving every element its proper chance