Insertion Sort for Nearly Sorted Array

Insertion Sort for Nearly Sorted Array

The Insertion Sort Algorithm is a simple comparison-based sorting algorithm that builds the sorted array one element at a time by inserting each element into its correct position in the sorted portion of the array. It is particularly efficient for nearly sorted arrays, where elements are close to their final positions, requiring fewer comparisons and shifts. This makes it ideal for scenarios where the input is already partially sorted.

Example:

• Input: nums = [2, 1, 3, 5, 4, 6] (nearly sorted)
• Output: [1, 2, 3, 4, 5, 6]
• Explanation: The array is sorted in ascending order.

Logic

Enter an array of numbers (comma-separated) to sort it using the Insertion Sort algorithm.

def insertionSort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        # Shift elements that are greater than key to the right
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        # Place key in its correct position
        nums[j + 1] = key
    return nums

# Example usage
nums = [2, 1, 3, 5, 4, 6]
print(insertionSort(nums))  # Output: [1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE