Colloquium Computer Science S. de Gouw
Date: |
Wednesday, January 18 2017 |
Speaker: |
Stijn de Gouw ( Open University and CWI, Amsterdam) |
Room: |
5161.0253 (Bernoulliborg) |
Time: |
15.00 |
Title:
Showing that Android's, Java's and Python's sorting algorithm is broken, and formally proving the fix
Abstract:
Tim Peters developed the Timsort hybrid sorting algorithm in 2002. It is a clever combination of ideas from merge sort and insertion sort, and designed to perform well on real world data. TimSort was first developed for Python, but later ported to Java (where it appears as java.util.Collections.sort and java.util.Arrays.sort) by Joshua Bloch (the designer of Java Collections who also pointed out that most binary search algorithms were broken ). TimSort is today used as the default sorting algorithm for Android SDK, Sun’s JDK and OpenJDK. Given the popularity of these platforms this means that the number of computers, cloud services and mobile phones that use TimSort for sorting is well into the billions.
Fast forward to 2015. After we had successfully verified Counting and Radix sort implementations in Java ( J. Autom. Reasoning 53(2), 129-139 ) with a formal verification tool called KeY , we were looking for a new challenge. TimSort seemed to fit the bill, as it is rather complex and widely used. Unfortunately, we weren’t able to prove its correctness. A closer analysis showed that this was, quite simply, because TimSort was broken and our theoretical considerations finally led us to a path towards finding the bug (interestingly, that bug appears already in the Python implementation). In this presentation, we show how we did it.
Colloquium coordinators are Prof.dr. M. Aiello (e-mail : M.Aiello rug.nl ) and
Prof.dr. M. Biehl (e-mail: M.Biehl rug.nl )
http://www.rug.nl/research/jbi/news/colloquia/computerscience
Last modified: | 10 February 2021 1.32 p.m. |
More news
-
24 March 2025
UG 28th in World's Most International Universities 2025 rankings
The University of Groningen has been ranked 28th in the World's Most International Universities 2025 by Times Higher Education. With this, the UG leaves behind institutions such as MIT and Harvard. The 28th place marks an increase of five places: in...
-
05 March 2025
Women in Science
The UG celebrates International Women’s Day with a special photo series: Women in Science.
-
16 December 2024
Jouke de Vries: ‘The University will have to be flexible’
2024 was a festive year for the University of Groningen. In this podcast, Jouke de Vries, the chair of the Executive Board, looks back.