Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

Second Edition · Android 11 · Kotlin 1.5 · IntelliJ IDEA Community Edition 2021.1

Before You Begin

Section 0: 7 chapters
Show chapters Hide chapters

Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 8 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 6 chapters
Show chapters Hide chapters

18. Quicksort
Written by Márton Braun

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

In the preceding chapters, you learned to sort a list using comparison-based sorting algorithms, such as merge sort and heap sort.

Quicksort is another comparison-based sorting algorithm. Much like merge sort, it uses the same strategy of divide and conquer. One important feature of quicksort is choosing a pivot point. The pivot divides the list into three partitions:

[ elements < pivot | pivot | elements > pivot ]

In this chapter, you’ll implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.

Example

Open the starter project. Inside QuicksortNaive.kt, you’ll see a naive implementation of quicksort:

fun <T : Comparable<T>> List<T>.quicksortNaive(): List<T> {
  if (this.size < 2) return this // 1

  val pivot = this[this.size / 2] // 2
  val less = this.filter { it < pivot } // 3
  val equal = this.filter { it == pivot }
  val greater = this.filter { it > pivot }
  return less.quicksortNaive() + equal + greater.quicksortNaive() // 4
}

This implementation recursively filters the list into three partitions. Here’s how it works:

  1. There must be more than one element in the list. If not, the list is considered sorted.
  2. Pick the middle element of the list as your pivot.
  3. Using the pivot, split the original list into three partitions. Elements less than, equal to or greater than the pivot go into different buckets.
  4. Recursively sort the partitions and then combine them.

Now, it’s time to visualize the code above. Given the unsorted list below:

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21]
                     *

Your partition strategy in this implementation is to always select the middle element as the pivot. In this case, the element is 8. Partitioning the list using this pivot results in the following partitions:

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
greater: [12, 9, 18, 27, 21]

Notice that the three partitions aren’t completely sorted yet. Quicksort will recursively divide these partitions into even smaller ones. The recursion will only halt when all partitions have either zero or one element.

Here’s an overview of all the partitioning steps:

Each level corresponds with a recursive call to quicksort. Once recursion stops, the leafs are combined again, resulting in a fully sorted list:

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

While this naive implementation is easy to understand, it raises some issues and questions:

  • Calling filter three times on the same list is not efficient.
  • Creating a new list for every partition isn’t space-efficient. Could you possibly sort in place?
  • Is picking the middle element the best pivot strategy? What pivot strategy should you adopt?

Partitioning strategies

In this section, you’ll look at partitioning strategies and ways to make this quicksort implementation more efficient. The first partitioning algorithm you’ll look at is Lomuto’s algorithm.

Lomuto’s partitioning

Lomuto’s partitioning algorithm always chooses the last element as the pivot. Time to look at how this works in code.

Step-by-step

Looking at a few steps of the algorithm will help you get a better understanding of how it works.

Hoare’s partitioning

Hoare’s partitioning algorithm always chooses the first element as the pivot. So, how does this work in code?

Step-by-step

Given the unsorted list below:

Effects of a bad pivot choice

The most important part of implementing quicksort is choosing the right partitioning strategy.

Dutch national flag partitioning

A problem with Lomuto’s and Hoare’s algorithms is that they don’t handle duplicates really well. With Lomuto’s algorithm, duplicates end up in the less than partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.

Step-by-step

Looking at an example using the unsorted list below:

Challenges

Challenge 1: Not using recursion

In this chapter, you learned how to implement quicksort recursively. Your challenge is to implement it iteratively. Choose any partition strategy you learned in this chapter.

Solution 1

You implemented quicksort recursively, which means you know what quicksort is all about. So, how might you do it iteratively? This solution uses Lomuto’s partition strategy.

Challenge 2: Provide an explanation

Explain when and why you would use merge sort over quicksort.

Solution 2

  • Merge sort is preferable over quicksort when you need stability. Merge sort is a stable sort and guarantees O(n log n). This is not the case with quicksort, which isn’t stable and can perform as bad as O(n²).
  • Merge sort works better for larger data structures or data structures where elements are scattered throughout memory. Quicksort works best when elements are stored in a contiguous block.

Key points

  • The naive implementation creates a new list on every filter function; this is inefficient. All other strategies sort in place.
  • Lomuto’s partitioning chooses the last element as the pivot.
  • Hoare’s partitioning chooses the first element as its pivot.
  • An ideal pivot would split the elements evenly between partitions.
  • Choosing a bad pivot can cause quicksort to perform in O(n²).
  • Median of three finds the pivot by taking the median of the first, middle and last element.
  • The Dutch national flag partitioning strategy helps to organize duplicate elements in a more efficient way.
17. Heap Sort
19. Graphs
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now