Patience Sort in Kotlin | Data Structures

Patience sort is just another O(n lg n) sorting algorithm (it actually depends on implementation). If you have played solitaire before, it's kind of similar. The algorithm maintains a list of stacks each of which is sorted in decreasing order (tail to head). The numbers are inserted incrementally.

To insert a number x, find the leftmost stack whose top element is larger than x and push x onto it. If no such stack exists create a new one at the end and push x onto it.

Notice that the way we insert numbers implies that top elements of the stacks are sorted in increasing order so the length of the longest increasing subsequence is just the number of piles at the end.

Once all numbers are inserted and the piles are ready, we'll repeatedly find the minimum number and write it to output. The stack from which we took the number must be inserted in a new position now so that the top elements of the stacks are sorted again. This can be done by using a heap to store the stacks.

If you simply scan the top elements to find the minimum and use no fancy data structures, the algorithm take O(n sqrt(n)) which is not bad for small n.

So this sorts the list of numbers and gives you the length of the LIS (and with some augmentation gives you a LIS).

Selection Sort

fun patienceSort(arr: Array<Int>) {
    if (arr.size < 2) return
    val piles = mutableListOf<MutableList<Int>>()
    outer@ for (el in arr) {
        for (pile in piles) {
            if (pile.last() > el) {

    for (i in 0 until arr.size) {
        var min = piles[0].last()
        var minPileIndex = 0
        for (j in 1 until piles.size) {
            if (piles[j].last() < min) {
                min = piles[j].last()
                minPileIndex = j
        arr[i] = min
        val minPile = piles[minPileIndex]
        if (minPile.size == 0) piles.removeAt(minPileIndex)

fun main(args: Array<String>) {
    val iArr = arrayOf(4, 65, 2, -31, 0, 99, 83, 782, 1)

Output of the Patience sort in Kotlin

[4, 65, 2, -31, 0, 99, 83, 782, 1]
[-31, 0, 1, 2, 4, 65, 83, 99, 782]			

Comb Sort

About Author

This article is written by Pavan, who is serving notice period in an MNC, Bangalore. He thought, let the articles speak rather than his image. He is also the same person who created the reporter for Protractor Jasmine

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions