/*
 * Mergesort.kt
 * 
 * This is Dave Musicant's Mergesort.kt from Fall 2024,
 * which was ported by Dave from the Mergesort code at
 * https://opendsa-server.cs.vt.edu/OpenDSA/Books/Everything/html/MergesortImpl.html
 * 
 * Modified lightly by Tanya Amert for Spring 2025.
 * 
 * Implements the Mergesort algorithm.
 */

// Entry point to mergesort: takes a MutableList of some type, assuming
// that elements of type T implement the Comparable interface
// (and thus can be compared to each other with < and >).
fun <T: Comparable<T>> mergesort(A: MutableList<T>) {
    _mergesort(A, A.toMutableList(), 0, A.count()-1)
}

// Recursive mergesort: uses a temp list to handle merge operations;
// modifies the list A to be in sorted order.
fun <T: Comparable<T>> _mergesort(A: MutableList<T>, temp: MutableList<T>, left: Int, right: Int) {
    // Base case: just one element
    if (left == right) {
        return
    }

    // Recursive case: divide and conquer
    val mid = (left+right)/2           // select midpoint
    _mergesort(A, temp, left, mid)     // mergesort left half
    _mergesort(A, temp, mid+1, right)  // mergesort right half

    // For the merge step, we'll copy the subarray into temp,
    // and then do the actual merging from temp back into A
    for (i in left..right) {
        temp[i] = A[i]
    }

    // Merge step
    var i1 = left
    var i2 = mid + 1
    for (curr in left..right) {
        if (i1 == mid+1) {               // left sublist exhausted
            A[curr] = temp[i2++]
        }
        else if (i2 > right) {           // right sublist exhausted
            A[curr] = temp[i1++]
        }
        else if (temp[i1] < temp[i2]) {  // get smaller value
            A[curr] = temp[i1++]
        }
        else{
            A[curr] = temp[i2++]
        }
    }
}

// Test our mergesort code.
fun main() {
    var list = mutableListOf(10, 4, 2, 1, 20, 29, 3, 2, 6)
    mergesort(list)
    println(list)
}