Kefan Yang Strider-Alex

## GSOC2018.md

      
              1 file
            
          
              0 forks
            
          
              0 comments
            
          
              0 stars
            
          
                Strider-Alex
                / GSOC2018.md
            
            
              Last active
              March 23, 2019 03:02
            
              
                GSOC 2018: Sorting algorithms benchmark and implementation
              
          
    Introduction

The goal of this project is to improve the sorting routine in PostgreSQL.
Currently, PostgreSQL is using 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. A fast sorting algorithms with guaranteed O(nlogn) time complexity would be preferable.
This project compared several sorting algorithms and proposed a new sorting implementation.
Benefits to the PostgreSQL Community


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