HomePhabricator

Fix PawSort (intro_sort and heap_sort)

Description

Fix PawSort (intro_sort and heap_sort)

Summary:
Implemented introspective sort :

  • DPQS;
  • pivots selected thanks to median-of-3 algo;
  • quitting recursive sort through depth (apply heap-sort) or threshold (number of item in array < 17).

Based on http://www.cs.rpi.edu/~musser/gp/introsort.ps

Test Plan: Added tests for insertion_sort.

Reviewers: jcmcdonald

Reviewed By: jcmcdonald

Subscribers: jcmcdonald, jenkins

Tags: Announce [Control], BSS [Team], PawLIB [Project], Programming [Dept]

Differential Revision: https://phabricator.mousepawmedia.net/D240

Details

Provenance
lulu731Authored on Sep 12 2018, 2:13 AM
lulu731Pushed on Sep 13 2018, 12:41 AM
Reviewer
jcmcdonald
Differential Revision
D240: Fix PawSort (intro_sort and heap_sort)
Parents
rP308ded5d7de2: Remove now-invalid pawlib-tester/include from linter paths
Branches
Unknown
Tags
Unknown