Function to perform insertion sort on subarray `a[low…high]`
| 6 | |
| 7 | // Function to perform insertion sort on subarray `a[low…high]` |
| 8 | void insertionsort(int a[], int low, int high) |
| 9 | { |
| 10 | // start from the second element in the subarray |
| 11 | // (the element at index `low` is already sorted) |
| 12 | for (int i = low + 1; i <= high; i++) |
| 13 | { |
| 14 | int value = a[i]; |
| 15 | int j = i; |
| 16 | |
| 17 | // find index `j` within the sorted subset a[0…i-1] |
| 18 | // where element a[i] belongs |
| 19 | while (j > low && a[j - 1] > value) |
| 20 | { |
| 21 | a[j] = a[j - 1]; |
| 22 | j--; |
| 23 | } |
| 24 | |
| 25 | // Note that the subarray `a[j…i-1]` is shifted to |
| 26 | // the right by one position, i.e., `a[j+1…i]` |
| 27 | |
| 28 | a[j] = value; |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | // Function to partition the array using Lomuto partition scheme |
| 33 | int partition(int a[], int low, int high) |