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!

You might want to write a base case to stop the recursion. If the sublist size is 1, stop trying to split it and just return it directly; it's already sorted. As an aside, it's faster to pass indices instead of copying lists. — ggorlen, Jun 13 '21 at 01:42
@ggorlen my god I hadnt noticed the base case was missing, thanks for pointing it out. I'm going to do the second thing you told me, thank you! — vale383, Jun 13 '21 at 02:06
You might be intested in knowing [why recursion can cause stack overflow, even with a base case](https://stackoverflow.com/questions/18368406/java-lang-stackoverflowerror-due-to-recursion) — mightyWOZ, Jun 13 '21 at 07:46

score 1 · Accepted Answer · answered Jun 13 '21 at 07:38

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.

Sort an array of pairs using mergesort gets stackoverflow

1 Answers1