// idea for how to sort [9, 2, 5] -> [2, 5, 9]...
// 
// idea: insert elements one at a time 
//       into a pre-sorted list!
// 

// insert(9, []) -> [9]

// insert(2, [9]) -> [2, 9]

// insert(5, [2, 9]) -> [2] + insert(5, [9]) -> [2] + [5, 9] -> [2, 5, 9]
// insert(5, [9]) -> [5, 9]
































// implements "insertion" sort
fun insertionSort(nums: List<Int>): List<Int> {
    fun insert(sortedList: List<Int>, num: Int): List<Int> {
        return when (sortedList.isEmpty()) {
            true -> listOf(num) // easy case
            false -> when (num <= sortedList[0]) {
                // num belongs at the start of the list
                true -> listOf(num) + sortedList

                // it belongs somewhere later,
                // keep the first element, recur!
                false -> sortedList.take(1) + insert(sortedList.drop(1), num)
            }
        }
    }
    
    return nums.fold(emptyList<Int>(), ::insert)
}

println(insertionSort(listOf(9, 2, 5))) // should be [2, 5, 9]