Which Data Structure Is Used by Insertion Sort?

//

Scott Campbell

Insertion sort is a simple sorting algorithm that is often used for small data sets or when the list is nearly sorted. It works by dividing the input into a sorted and an unsorted region, and iteratively inserting elements from the unsorted region into their correct position in the sorted region. But have you ever wondered which data structure is used by insertion sort to achieve this?

The Array Data Structure

The main data structure used by insertion sort is the array. An array is a collection of elements of the same type, stored in contiguous memory locations. In insertion sort, we use an array to represent our list of elements that need to be sorted.

Let’s say we have an array [5, 2, 4, 6, 1, 3] that needs to be sorted in ascending order using insertion sort. We start with the first element as our sorted region and iterate through the remaining elements in the unsorted region.

The Sorted and Unsorted Regions

The key idea behind insertion sort is that at each iteration, we take an element from the unsorted region and insert it into its correct position in the sorted region. Initially, our sorted region consists of only one element – the first element of the array.

  • Step 1: Our initial array: [5, 2, 4, 6, 1, 3].
  • Step 2: The sorted region contains only one element: [5]. The unsorted region contains all other elements.
  • Step 3: We take the first element from the unsorted region (i.e., 2) and compare it with each element in the sorted region (i., 5). We find that 2 should be inserted before 5.
  • Step 4: After inserting 2, our sorted region becomes: [2, 5]. The unsorted region becomes: [4, 6, 1, 3].
  • Step 5: We repeat the process for the next element in the unsorted region (i., 4).

    We compare it with each element in the sorted region ([2, 5]) and insert it at the correct position.

  • Step 6: After inserting 4, our sorted region becomes: [2, 4, 5]. The unsorted region becomes: [6, 1, 3]
  • Step 7: We continue this process until we have inserted all elements from the unsorted region into their correct positions in the sorted region. At each step, we are essentially shifting elements to make space for the new element being inserted.

The Role of Arrays in Insertion Sort

The array data structure plays a crucial role in insertion sort. It allows us to access elements by their indices and efficiently move elements within the array. When we insert an element into its correct position, we shift all larger elements to the right to make room for it.

In summary, insertion sort uses arrays as its main data structure. The sorted and unsorted regions are represented by subarrays within the main array.

Elements from the unsorted region are iteratively inserted into their correct positions in the sorted region by shifting larger elements to the right. This process continues until all elements are sorted.

Now that you know which data structure is used by insertion sort, you can better understand its time complexity and space complexity. Arrays provide a simple and efficient way to implement insertion sort, making it a popular choice for small or nearly sorted lists.