How to Implement Insertion Sort in Batch Script

In data processing, Insertion Sort is an efficient way to sort a small list of items, especially if the list is already "mostly sorted." It works the way many people sort playing cards in their hands: you take one item at a time and "insert" it into its correct position among the items you've already sorted. For small-scale Batch scripts managing configuration keys or task lists, it is a robust alternative to Bubble or Selection sort.

In this guide, we will demonstrate how to implement the Insertion Sort algorithm in a Batch environment.

The Strategy: The Shifting Slide

1. Start from the second element.
2. Compare it with the items before it.
3. "Slide" the larger items forward to make a gap.
4. "Insert" the current item into the correct gap.

note

Insertion Sort has a best-case time complexity of O(n) when the list is already sorted, making it the fastest simple sort for nearly-ordered data. Its average and worst-case complexity is O(n²).

Implementation Script

@echo off
setlocal enabledelayedexpansion

:: 1. Define the Array
set "size=5"
set "ARR_1=64"
set "ARR_2=25"
set "ARR_3=12"
set "ARR_4=22"
set "ARR_5=11"

echo Unsorted: !ARR_1! !ARR_2! !ARR_3! !ARR_4! !ARR_5!

:: 2. Insertion Sort Algorithm
:: Outer loop starts at the second element
for /L %%i in (2,1,%size%) do (
    call set "key=%%ARR_%%i%%"
    set /a "j=%%i - 1"

    :: Inner loop: Shift elements that are greater than 'key'
    call :shift_loop

    :: Place the 'key' in its correct spot
    set /a "insertPos=j + 1"
    set "ARR_!insertPos!=!key!"
)

echo Sorted:   !ARR_1! !ARR_2! !ARR_3! !ARR_4! !ARR_5!

endlocal
pause
exit /b 0

:: ============================================
:: SHIFT SUBROUTINE
:: ============================================
:shift_loop
if !j! LSS 1 exit /b
for %%m in (!j!) do set "valJ=!ARR_%%m!"
if !valJ! GTR !key! (
    set /a "next=j + 1"
    set "ARR_!next!=!valJ!"
    set /a "j-=1"
    goto :shift_loop
)
exit /b

Why Use Insertion Sort?

1. Efficiency for Small Lists: It is often faster than Selection or Bubble Sort for small datasets because it has very low overhead.
2. Stable Sorting: If two items have the same value, they remain in their original relative order.
3. Adaptive: If the list is already sorted, Insertion Sort finishes almost instantly (O(n) time), making it ideal for checking or "fixing" nearly complete lists.

Important Limitations

warning

Batch arithmetic (set /a) and comparisons (if GTR, if LSS) only work with signed 32-bit integers (approximately ±2.1 billion). Decimal values and numbers exceeding this range cannot be sorted with this method. For such cases, use the PowerShell bridge.

1. Performance: Like other simple sorts, it is O(n²) for average/worst-case scenarios. Do not use this for arrays with more than 100–200 items in Batch.
2. Integer Logic: Batch can only sort whole numbers. Logic involving decimals will fail.
3. Variable Limit: Large arrays consume more of the environment variable memory space.

Best Practices

1. Interactive Updates: If you allow users to add items to a sorted list one-by-one, using Insertion Sort to place each new item is significantly faster than re-sorting the entire list from scratch.
2. Error Handling: Ensure the size variable matches the actual number of elements in your array, or the loop will attempt to sort "Undefined" variables.

tip

To sort in descending order, change if !valJ! GTR !key! to if !valJ! LSS !key! in the shift subroutine. This causes larger values to remain in place while smaller values are shifted forward, producing a high-to-low ordering.

Conclusion

Implementing Insertion Sort adds a layer of professionalism and efficiency to your data management scripts. By using the "Slide and Insert" methodology, you ensure that your lists, from prioritized server tasks to alphabetical user registries, are always perfectly organized with minimal computational waste. This algorithmic knowledge allows you to build scripts that feel fast and responsive even when handling complex internal logic.