=======================
Insert-Sort Performance
=======================

.. include:: performance_compared.txt     


------------
Integer Sets
------------

The following figures show the running time of inserting integers one by one into a set and iterating in sorted order after every insertion, as a function of the number of integers (see :download:`_set_insert_sort.py` for the source).
    

The following figure shows the performance of all the implementations:

.. figure:: IntSetInsertSortAll.png

The following figure shows the performance of all implementations with similar performance:

.. figure:: IntSetInsertSortAllNoBlistBintrees.png

As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:

.. figure:: IntSetInsertSortCompetitiveLarger.png


-----------
String Sets
-----------

The following figures show the running time of inserting strings one by one into a set and iterating in sorted order after every insertion, as a function of the number of integers (see :download:`_set_insert_sort.py` for the source).
    

The following figure shows the performance of all the implementations:

.. figure:: StrSetInsertSortAll.png

The following figure shows the performance of all implementations with similar performance:

.. figure:: StrSetInsertSortAllNoBlistBintrees.png

As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:

.. figure:: StrSetInsertSortCompetitiveLarger.png


-------------
Integer Dicts
-------------

The following figures show the running time of inserting integers one by one into a dict and iterating in sorted order after every insertion, as a function of the number of integers (see :download:`_set_insert_sort.py` for the source).
    

The following figure shows the performance of all the implementations:

.. figure:: IntDictInsertSortAll.png

The following figure shows the performance of all implementations with similar performance:

.. figure:: IntDictInsertSortAllNoBlistBintrees.png

As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:

.. figure:: IntDictInsertSortCompetitiveLarger.png


------------
String Dicts
------------

The following figures show the running time of inserting strings one by one into a dict and iterating in sorted order after every insertion, as a function of the number of integers (see :download:`_set_insert_sort.py` for the source).
    

The following figure shows the performance of all the implementations:

.. figure:: StrDictInsertSortAll.png

The following figure shows the performance of all implementations with similar performance:

.. figure:: StrDictInsertSortAllNoBlistBintrees.png

As the number of items increases, the cost of sorting incurred by the hash-based implementation grows. This is shown in the following figure, where larger numbers of items were used:

.. figure:: StrDictInsertSortCompetitiveLarger.png