Repository: TheAlgorithms/C-Plus-Plus
File: sorting/insertion_sort_recursive.cpp (C++)

Code before:
 * @details
 * Insertion sort is a simple sorting algorithm that builds the final
 * sorted array one element at a time. It is much less efficient compared
 * to other sorting algorithms like heap sort, merge sort, or quick sort.
 * 
 * However, it has several advantages:
 * - Easy to implement.
 * - Efficient for small data sets.
 * - More efficient than other O(n²) algorithms like selection sort or bubble sort.
 * - Stable: it does not change the relative order of elements with equal keys.
 * 
 * Insertion sort works similarly to how people sort playing cards in their hands.
 * The algorithm iterates through the list and inserts each element into its correct 
 * position in the sorted portion of the array.
 *
 * Example execution:
 * 1. Start with the array [4, 3, 2, 5, 1].
 * 2. Insert 3 in its correct position: [3, 4, 2, 5, 1].
 * 3. Insert 2: [2, 3, 4, 5, 1].
 * 4. Continue this until the array is sorted: [1, 2, 3, 4, 5].
 */

#include <algorithm>   ///< for std::is_sorted
#include <cassert>     ///< for assert function in testing
#include <iostream>    ///< for std::cout and std::endl
#include <vector>      ///< for using std::vector

/** 
 * @namespace sorting
 * @brief Contains sorting algorithms
 */
namespace sorting {

/**
 * @brief Insertion Sort Function
 * 
 * @tparam T Type of the array elements
 * @param [in,out] arr Array to be sorted
 * @param n Size of the array
 */
template <typename T>
void insertionSort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int j = i - 1;
        while (j >= 0 && temp < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }

Review comment (suggestion):
```suggestion
#include <algorithm>   /// for std::is_sorted
#include <cassert>     /// for assert function in testing
#include <iostream>    /// for std::cout and std::endl
#include <vector>      /// for using std::vector
```


Code after:
 * 
 * @details
 * Insertion sort is a simple sorting algorithm that builds the final
 * sorted array one element at a time. It is much less efficient compared
 * to other sorting algorithms like heap sort, merge sort, or quick sort.
 * 
 * However, it has several advantages:
 * - Easy to implement.
 * - Efficient for small data sets.
 * - More efficient than other O(n²) algorithms like selection sort or bubble sort.
 * - Stable: it does not change the relative order of elements with equal keys.
 * 
 * Insertion sort works similarly to how people sort playing cards in their hands.
 * The algorithm iterates through the list and inserts each element into its correct 
 * position in the sorted portion of the array.
 * 
 * The time complexity of the algorithm is \f$O(n^2)\f$, and in some cases, it
 * can be \f$O(n)\f$.
 * 
 * Example execution:
 * 1. Start with the array [4, 3, 2, 5, 1].
 * 2. Insert 3 in its correct position: [3, 4, 2, 5, 1].
 * 3. Insert 2: [2, 3, 4, 5, 1].
 * 4. Continue this until the array is sorted: [1, 2, 3, 4, 5].
 */


#include <algorithm>   /// for std::is_sorted
#include <cassert>     /// for assert function in testing
#include <iostream>    /// for std::cout and std::endl
#include <vector>      /// for using std::vector

/** 
 * @namespace sorting
 * @brief Contains sorting algorithms
 */
namespace sorting {

/**
 * @brief Insertion Sort Function
 * 
 * @tparam T Type of the array elements
 * @param[in,out] arr Array to be sorted
 * @param n Size of the array
 */
template <typename T>
void insertionSort(T *arr, int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int j = i - 1;
        while (j >= 0 && temp < arr[j]) {