UNIVERSITY OF SOUTHERN MINDANAO
Insertion Sort
Algorithm
Prepared by: Group 3
Insertion Sort
• based on natural human sorting behavior
• efficient for small data sets
• often used for sorting small lists
• works by iteratively inserting each element of an unsorted list
into its correct position in a sorted portion of the list.
• works mainly by shifting elements rather than
swapping each element in turn
2
Example:
3
Cont..
4
Insertion
Sort
Outer loop: controls how
FOR i = 1 to length of array - 1 many elements we process.
SET key = array[i] Inner loop: handles the
SET j = i - 1 shifting process.
WHILE j >= 0 AND array[j] > key
SET array[j + 1] = array[j] Optimization: aim to reduce
DECREMENT j by 1 the time for finding the
correct position without
affecting the overall
SET array[j + 1] = key performance.
5
Implementation
• Function to sort array using insertion sort
6
Implementation Cont..
• Utility function to print array of size n
Output:
2457
7
Properties of Insertion Sort
• In-Place Sorting: It sorts the array directly by
rearranging elements within the same array without
using significant additional memory.
• Method of Operation: Relies on shifting
elements rather than swapping, minimizing the
number of data movements.
8
Time Complexity
• Best Case: (O(n)): when the input list is already
sorted.
• Average Case: (O(𝑛2)): If the list is randomly ordered.
• Worst case: (O(𝑛2)): If the list is in reverse order.
9
Space Complexity
• (O(1))
Space complexity is O(1) because an extra variable key is used
10
Uses and Applications
• Simple and easy to implement.
• Stable sorting algorithm.
• The array has a limited amount of elements.
• Only a few components remain to be sorted.
• Space-efficient as it is an in-place algorithm.
11
When Should it be used?
• Small Input Sizes
• Partially Sorted Arrays
• Nearly Sorted Arrays
• Stable Sorting
• Simple Implementations
12
Limitations of Insertion Sort
• Quadratic Time Complexity: O(n²) in worst/average case, inefficient for large
datasets.
• Lack of Scalability: Not suitable for large input sizes.
• Inefficient for Random Arrays: Requires many comparisons and shifts, making it
slow for unordered data.
13
Visual Example
14
Advantages and Disadvantages
15
Comparison with other Algorithms
16
Reference
GeekforGeeks. (n.d.). Insertion sort algorithm. GeeksforGeeks. Retrieved
December 3, 2024, from https://www.geeksforgeeks.org/insertion-sort-
algorithm/?ref=lbp
Logicmojo. (n.d.). Insertion sort. Logicmojo. Retrieved December 3, 2024, from
https://logicmojo.com/insertion-sort
Bro Code. (2020, April 10). Insertion sort algorithm | Learn Insertion Sort |
BroCode. YouTube. Retrieved December 3, 2024, from
https://www.youtube.com/watch?v=8mJ-OhcfpYg&t=243s
ChatGPT. (n.d.). ChatGPT: Your AI language model. ChatGPT. Retrieved December
3, 2024, from https://chatgpt.com/
subtitle
