Merge Sort Python Iterative and Recursive implementations

Merge sort is a famous sorting algorithm with guarantee running time N Log N. However, this algorithm uses extra space equivalent to N. The algorithms uses a divide and conquer approach where an is divided in two and sorted, then the two sorted halves are merged. This post shows the Merge Sort Python implemented in two ways: Recursively and Iteratively. The implementation were done in Python to explore a different approach than the traditional C and Java languages.

System Configuration

The following are the system configuration used for benchmarking:

Python version: 2.7.5
Operating System: OS X 10.9.4
RAM Memory: 8GB
Processor 2.4 GHz Intel Core i5

Merge Sort Recursive:

The recursive version of Merge Sort Python was implemented using the traditional divide and conquer paradigm: Divide the array in two, sort each half and then merge them.

The implementation works for any array size and it was Unit Tested.

The benchmark include a range of unsorted list of sizes 2 to 1048576. This algorithm guarantees a running time N log N. However, it needs extra space equivalent to N when merging.

Table 1 in the Appendix shows the time taken to sort the different input sizes. Figure 1 show the log-log plot of the running time as a function of the input size. In this plot we can see that the implementation of the algorithms is running as expected. The plot shows a linearithmic order of grow of the function.

Screen Shot 2015-01-19 at 9.47.54 pm

Merge Sort Iterative

For the iterative version of Merge Sort Algorithm the implementation is merging single elements into pairs, then pairs into quads, then quads into octets, etc. Doing it this ways the implementation avoid using an stack and works for even and odd input sizes.

The implementation works for any array size.

Figure 2 show the log-log plot of the running time as a function of the input size. The plot shows a linearithmic order of grow of the function.

Screen Shot 2015-01-19 at 9.48.06 pm

When comparing both implementation of the algorithms there is not much difference in the running time. However, when these implementations were compared to the Python built in sort function running time there is some constant difference. For instance, for an input of 1 million elements Python’s sort function was 13 times faster. Python running time was just under a second and my implementation was around 13 seconds average. Refer to figure 3

Screen Shot 2015-01-19 at 9.48.15 pm

 

Code Implementation

 

Leave a Reply

Your email address will not be published. Required fields are marked *