Sort an array of pairs using mergesort gets stackoverflow

Question

I have the array A = arrayOf(Pair(1,1),Pair(0,9),Pair(3,8),Pair(4,0),Pair(6,6),Pair(10,7),Pair(5,1),Pair(7,3)) in Kotlin and I want to sort it with mergesort based on the X component of the pairs.

So far I have this

fun merge(U: Array<Pair<Int,Int>>, V: Array<Pair<Int,Int>>, A: Array<Pair<Int,Int>>) {
    var i: Int = 0
    var j: Int = 0
    var size = U.size + V.size

    for (k in 0 until size) {
        if ((i < U.size)&&(j < V.size)) {
            if (U[i].component1() < V[i].component1()) {
                A[k] = U[i]
                i = i + 1
            }
            else {
                A[k] = V[j]
                j = j + 1
            }
        }    
    }
}

fun mergeSort(A: Array<Pair<Int,Int>>) {
    var middle = A.size / 2
    var U = A.copyOfRange(0, middle)
    var V = A.copyOfRange(middle, A.size)
    mergeSort(U)
    mergeSort(V)
    merge(U, V, A)
}

However, it gives me a stackoverflow error. I don't know what could be the cause of it. Is there a better way to do this?

edit: @ggorlen pointed out that I was missing the base case, which after checking, I had accidentally deleted while modifying the mergesort function. Thanks!

Answer 1

Your recursive procedure is missing the base case, without this your procedures falls in a loop where it calls itself indefinitely and ultimately causes the stack overflow.

When it comes to writing recursive procedures one must understand that there are two cases that must be clearly defined.

1. Recursive case : When recursive procedure calls itself (Recursion)

2. Base case : When recursion bottoms out (In your case this happens when array contains single item, in which case its already sorted, no need to recurse)

Base case is very important property of a recursive procedure, since its responsible for stopping the procedure from falling in an endless recursion.