[Verse 1]
Start with an array, elements scattered around
Pick the second one, that's where we get down
Compare it left, find where it belongs
Shift everything right, keep the sorted strong
Like organizing cards in your hand so neat
Each new element finds its perfect seat
From left to right we build our sorted zone
One insertion at a time, position by position grown
[Chorus]
Insert and sort, left to right
Key in hand, find the right sight
Shift them over, make some space
Every element finds its place
Insert and sort, building clean
Best sorted array you've ever seen
Start from one, work to the end
Insertion sort, your sorting friend
[Verse 2]
Current key stored safe before we start
Search backwards through the sorted part
While elements greater than our key we see
Shift them right by one degree
Found the spot where key should go
Insert it there, watch order flow
Inner loop handles the shifting game
Outer loop keeps the forward claim
[Chorus]
Insert and sort, left to right
Key in hand, find the right sight
Shift them over, make some space
Every element finds its place
Insert and sort, building clean
Best sorted array you've ever seen
Start from one, work to the end
Insertion sort, your sorting friend
[Bridge]
O of n squared in the worst case scene
But when data's nearly sorted, it's lean
Adaptive algorithm, stable and true
In-place sorting with memory few
Small datasets love this technique
Efficient when the array's not too big
Simple to code, easy to trace
Insertion sort knows its rightful place
[Verse 3]
From index one we start our quest
Index zero already passed the test
For each position, grab that key
Find where it lives in sorted harmony
While loop running, shifting right
Until we find that perfect sight
Drop the key in its new home
Sorted portion continues to grow and roam
[Chorus]
Insert and sort, left to right
Key in hand, find the right sight
Shift them over, make some space
Every element finds its place
Insert and sort, building clean
Best sorted array you've ever seen
Start from one, work to the end
Insertion sort, your sorting friend
[Outro]
When the array's small and you need it clean
Insertion sort's the sorting machine
One by one, piece by piece
Until every element finds its peace