[Learning Documents] [Golang] Go 1.19 Sort is Faster

title: [Learning Document][Golang] Go 1.19's Sort is Faster
published: false
date: 2022-08-18 00:00:00 UTC
tags: 
canonical_url: http://www.evanlin.com/til-go-pd-quicksort/
---

![image-20220819163803756](http://www.evanlin.com/images/2021/image-20220819163803756.png)

## Go 1.19's Sort is Faster

Go 1.19's Sort has been changed from QuickSort to Pattern-Defeating #Quicksort, the same as #Rustlang and C++ #Boost.

If you want to know more about PD Quicksort, you can [refer to this article by the ByteDance team ""Building the fastest sorting algorithm for Go language"" (Simplified Chinese)](https://blog.csdn.net/ByteDanceTech/article/details/124464192)

### Quick explanation of what PD Quicksort is?

- Optimized from QuickSort, best case from O(n log n) –> O(n)
- Worst case O(n log n)

## Related articles:

- Image from slides (Japanese): [https://speakerdeck.com/po3rin/go1-dot-19decai-yong-sareta-pattern-defeating-quicksort-falseshao-jie](https://speakerdeck.com/po3rin/go1-dot-19decai-yong-sareta-pattern-defeating-quicksort-falseshao-jie)

- Algorithm implementation: [https://github.com/orlp/pdqsort](https://github.com/orlp/pdqsort)
- Author's explanation video: [https://www.youtube.com/watch?v=jz-PBiWwNjc](https://www.youtube.com/watch?v=jz-PBiWwNjc)
- [Golang's sorting algorithm will be changed to pdqsort, LLVM libc++ changed to BlockQuicksort](https://blog.gslin.org/archives/2022/04/22/10673/golang-%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95%E5%B0%87%E6%8F%9B%E6%88%90-pdqsort%EF%BC%8Cllvm-libc-%E6%8F%9B%E6%88%90-blockquicksort/)