GSOC 2018:Sorting algorithms benchmark and implementation

From PostgreSQL wiki
Jump to: navigation, search


This project tries to improve the current sorting routine used in PostgreSQL.

Originally, PostgreSQL is using the QuickSort implemented by J. L. Bentley and M. D. McIlroy in "Engineering a sort function" with some modifications. This sorting routine is very fast, yet may fall to O(n^2) time complexity in the worst case scenario. I am trying to find faster sorting algorithms with guaranteed O(nlogn) time complexity.

In this project, I have compared several sorting algorithms and proposed a new sorting implementation.

Benefits to the PostgreSQL Community

  • Using a more optimized sorting algorithm could bring a performance gain for many parts of PostgreSQL.
  • The benchmark could be used for further improvement of the sorting routine.


Proposal archive:



  • New hash table implementation