3
\$\begingroup\$

I started learning kotlin recently,with some background in java.

So I wrote a merge sort algorithm in kotlin. I am looking for best practices in kotlin and looking for this code review.

I also wanted to know about its efficiency and ways to increase it.

Thanks

fun merge(list: List<Int>,lo: Int,hi: Int): List<Int>{
    val mid=(lo+hi)/2
    var i=lo
    var j=mid+1
    var new_list=mutableListOf<Int>()
    for(k in 0..(lo-1)) new_list.add(list[k])
    while(!(i==mid+1 && j==hi+1)){
        if(i==mid+1){
            new_list.add(list[j])
            j++
        }
        else if(j==hi+1){
            new_list.add(list[i])
            i++
        }
        else if(list[i]>list[j]){
            new_list.add(list[j])
            j++
        }
        else{
            new_list.add(list[i])
            i++
        }
    }
    for(k in (hi+1)..(list.size-1)) new_list.add(list[k])
    return new_list.toList()
}

fun mergeSort(list: List<Int>,lo: Int,hi: Int): List<Int>{
    if(lo<hi){
        val mid=(lo+hi)/2
        val list1=mergeSort(list,lo,mid)
        val list2=mergeSort(list1,mid+1,hi)
        val list3=merge(list2,lo,hi)
        return list3
    }
    return list
}
\$\endgroup\$
2
\$\begingroup\$

Performance

The performance is not good because you have to create very many lists (var new_list=mutableListOf<Int>()). I rewrote merge sort (see below) and I tried benchmarking it against your code, but my code would sort through a million long list in a fraction of second while yours would take many seconds for a list of just a few thousand elements.

You can look for example at the faster implementation on wikipedia where only two work arrays are used. This is what I coded below.

The choice of data structure also affects the performance. You should probably have used an Array<Int> instead of List<Int>. It just so happens that mutableListOf() creates an ArrayList which is basically a raw array underneath (same as Array<Int>). But I had to check that. If mutableListOf() had created a linked list instead, you would have had worse performance. Although it would not change the performance, you should stick with Array so not everyone will have to look at what is actually underneath mutableListOf().

Array<Int> is not even the best you can do: Array<Int> corresponds to a Java Integer[], but Kotlin has IntArray which corresponds to int[]. The latter is better for performance because there is no boxing/unboxing related to using an Integer instead of a raw int.

Generics

Instead of hard coding for Int, you could have made your code more general by defining your functions such as:

fun <T: Comparable<T>> mergeSort(list: Array<T>,lo: Int,hi: Int): List<T> { ... }

You could use it for Double, String, or any other class which implements Comparable.

I gave you contradictory advice: I just recommended using Array<T>, but above I recommended IntArray. From a software engineering perspective Array<T> wins, but from a performance stand point, IntArray wins. There is no easy answer. I would usually go for code re-usability, but for something that is performance critical like a sorting algorithm, it's probably better to go with IntArray.

Fuction merge

I don't like this function.

  • The name is quite confusing to start with: it is called merge, but there is only one input array. Maybe mergeSortedHalves would be better.
  • This function should not be publicly accessible. Either it should be internal, or define directly within function mergeSort.
  • The mid value should be a function parameter too. It would give a better function signature to understand what the function is doing. But most importantly it is quite dangerous as it is. You compute mid in both merge and mergeSort. The computations agree now, but maybe you'll change the computation in one place to always round down and forget to update the other mid computation. Everything would break down.
  • Performance tip: before and after the main while-loop, you make copies of parts of arrays using for-loops. If you had been using Arrays it would have been much faster to use instead System.arraycopy(). But more generally you should not copy this possibly huge array when all you want to do is swap a few values in a small section. This is why your algorithm performs poorly.

Nitpicking

A small detail, but you don't use spaces in the standard way, for Java or Kotlin. There should be a space before { and there should be spaces around =, ==, <, etc. There is also a space after if, while and for.

Code Sample

Here is my implementation using IntArray. You can look at the benchmarking I did with different implementations in this gist. Your function is not benchmarked because it could not sort my target lists which have a million items.

/**
 * @param array The array to sort.  A copy is made, so it's content is not modified.
 */
fun mergeSortIA(array: IntArray) : IntArray {
    val arrayCopy = array.copyOf()
    val arrayCopy2 = array.copyOf()

    sortSectionIA(arrayCopy, arrayCopy2, 0, arrayCopy.size)

    return arrayCopy2
}

/**
 * Sorts the specified section of the array.
 *
 * @param workA Should contain identical values as workB in the specified range.
 *              The final values in the specified range are destroyed (actually they are made
 *              of two adjacent sorted ranged).
 * @param workB Should contain identical values as workA in the specified range.
 *              The final values in the specified range are the sorted values in that range.
 */
internal inline fun mergeHalvesIA(workA: IntArray,
                                  workB: IntArray,
                                  start: Int,
                                  mid: Int,
                                  exclusiveEnd: Int) {
    var p1 = start
    var p2 = mid
    for (i in start until exclusiveEnd) {
        if (p1 < mid && (p2 == exclusiveEnd || workA[p1] <= workA[p2])) {
            workB[i] = workA[p1]
            p1++
        } else {
            workB[i] = workA[p2]
            p2++
        }
    }
}

internal fun sortSectionIA(input: IntArray,
                           output: IntArray,
                           start: Int,
                           exclusiveEnd: Int) : Unit {

    if (exclusiveEnd - start <= 1)
        return
    val mid = (start + exclusiveEnd) / 2
    sortSectionIA(output, input, start, mid)
    sortSectionIA(output, input, mid, exclusiveEnd)
    mergeHalvesIA(input, output, start, mid, exclusiveEnd)
}

Multi-Threaded Implementation (Advanced)

I recommended for performance that instead of creating new lists at each iteration, you should work with only two work arrays. However if you wanted to write a version of merge sort which uses many threads in parallel, you would have to create many arrays (but shorter arrays, not full length copies at each iteration as you do). I did implement that too, you can look at my gist.

But I had to use a trick to avoid creating very many tiny arrays: when the function is called on a array of size 128 or smaller, instead of calling the multi-threaded function recursively, it calls the basic version of merge sort which uses the two working arrays, and runs on the current thread.

\$\endgroup\$
2
\$\begingroup\$

I have zero experience with Kotlin, but I can tell you how to make your implementation run faster. You could allocate the auxiliary space only once throughout the entire algorithm, and you essentially merge from one array to other, then at a higher recursion level, you swap their roles and merge in opposite direction. You can learn about this approach here.

Also, one nitpick: in most languages (I know), the sorting method/function does not return any list; they just modify the input array.

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ What "Scala and Python" have to do with Kotlin??? \$\endgroup\$ – coderodde Aug 27 '17 at 3:02
  • \$\begingroup\$ Scala has a lot to do with Kotlin, look it up. \$\endgroup\$ – Tamoghna Chowdhury Aug 27 '17 at 5:40
  • \$\begingroup\$ I guess you don't know Scala or Python then (Python has both the mutating sort and the pure sorted functions, all of Scala's sort functions are pure) \$\endgroup\$ – Tamoghna Chowdhury Aug 27 '17 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.