.. _recSorting:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "recSorting";ODSA.SETTINGS.MODULE_LONG_NAME = "Recursive Sorting";ODSA.SETTINGS.MODULE_CHAPTER = "Miscellaneous"; ODSA.SETTINGS.BUILD_DATE = "2016-09-25 20:47:44"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2016 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Sally Hamouda
   :satisfies: recursive sorting
   :topic: Recursive Sorting

Recursive Sorting
=================

In looking for a recursive solution, you should first discover what characteristics of sorting make it a recursive problem. In order for any problem to be solved recursively it must satisfy:

1- There must be some way to break large problems down into simpler instances of the same problem.

2- Assuming that each of those subproblems can be solved by successive applications of the recursive procedure, there must be some way to generate a solution to  the original problem from the solution to each of these smaller parts.

3- We must be able to determine a set of simple cases which can be solved diectly, without any further decomposition.


The next exercises will ask you to implement variations of merge sort.