Insertion Sort Solution for TCS NQT
Company: TCS NQT · Difficulty: Easy · Topics: Array, Sorting
Problem Statement
Implement the insertion sort algorithm to sort an array of integers in ascending order. Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Examples
Example 1:
Input: arr = [12, 11, 13, 5, 6]
Output: [5, 6, 11, 12, 13]
Explanation:
- Pass 1: [12] (first element is sorted)
- Pass 2: [11, 12] (insert 11 before 12)
- Pass 3: [11, 12, 13] (insert 13 after 12)
- Pass 4: [5, 11, 12, 13] (insert 5 at beginning)
- Pass 5: [5, 6, 11, 12, 13] (insert 6 after 5)
Example 2:
Input: arr = [64, 34, 25, 12, 22, 11, 90]
Output: [11, 12, 22, 25, 34, 64, 90]
Explanation: The array is sorted by repeatedly inserting elements into their correct positions.
Example 3:
Input: arr = [1]
Output: [1]
Explanation: Single element array is already sorted.
Example 4:
Input: arr = [3, 3, 3, 3]
Output: [3, 3, 3, 3]
Explanation: Array with duplicate elements remains the same after sorting.
Intuition
Insertion sort works by dividing the array into two parts:
1. Sorted region: Initially contains only the first element, grows from left to right
2. Unsorted region: Contains the remaining elements
In each iteration:
1. Take the first element from the unsorted region
2. Insert it into the correct position in the sorted region
3. Expand the sorted region by one element
4. Repeat until the unsorted region is empty
The key insight is that we maintain the sorted region and insert new elements into their correct positions by shifting elements as needed.
Approach
Approach 1: Standard Insertion Sort
1. Start with the second element (index 1)
2. Compare it with all previous elements
3. Shift elements to make space for insertion
4. Insert the element in its correct position
5. Repeat for all remaining elements
Approach 2: Binary Search Insertion Sort
1. Use binary search to find the correct insertion position
2. This reduces the number of comparisons but not shifts
3. Still O(n²) due to shifting operations
Approach 3: Recursive Insertion Sort
1. Sort the first n-1 elements recursively
2. Insert the nth element into the sorted array
3. Uses more space due to recursion
Dry Run
Let's trace through Example 1: arr = [12, 11, 13, 5, 6]
Pass 1 (i=1, key=11):
- Compare 11 with 12: 11 < 12, shift 12 right
- Insert 11 at position 0: [11, 12, 13, 5, 6]
Pass 2 (i=2, key=13):
- Compare 13 with 12: 13 > 12, no shift needed
- Insert 13 at position 2: [11, 12, 13, 5, 6]
Pass 3 (i=3, key=5):
- Compare 5 with 13: 5 < 13, shift 13 right
- Compare 5 with 12: 5 < 12, shift 12 right
- Compare 5 with 11: 5 < 11, shift 11 right
- Insert 5 at position 0: [5, 11, 12, 13, 6]
Pass 4 (i=4, key=6):
- Compare 6 with 13: 6 < 13, shift 13 right
- Compare 6 with 12: 6 < 12, shift 12 right
- Compare 6 with 11: 6 < 11, shift 11 right
- Compare 6 with 5: 6 > 5, insert 6 at position 1: [5, 6, 11, 12, 13]
Final result: [5, 6, 11, 12, 13]
Key Insights
1. Stable: Insertion sort is a stable sorting algorithm
2. In-place: No extra space required (O(1) space complexity)
3. Adaptive: Efficient for partially sorted arrays
4. Simple: Easy to understand and implement
5. Online: Can sort a list as it receives it
Edge Cases
1. Empty array: Return empty array
2. Single element: Return the element as is
3. Already sorted: Very efficient, O(n) time complexity
4. Reverse sorted: Worst case, O(n²) time complexity
5. Duplicate elements: Will work correctly and preserve order
Time and Space Complexity
- Time Complexity: O(n²) in worst and average case, O(n) in best case (already sorted)
- Space Complexity: O(1) - in-place sorting algorithm