Mergesort algorithm in python

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example if the data to be sorted is in a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly and in Quicksort we have to access data randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

Pursuit towards finding equations and algorithms for happiness

A simple algorithm for improving your happiness index ?  Is there any such proven formula ? Because if you carefully notice, one or the other way everyone pursue what brings happiness to them. May be its different for different people at different occasions, but truth is we follow what we regard as happiness. Humans and Animals live that way and the only difference in humans is that he or she is having more perseverance than most other Animals when happiness is pursued. In Animals its most of the time instantaneous. So how smart is it to think about generic equations and algorithms which can save the world ?

Some people call that perseverance you follow as your ego or some times its treated as greed and sometimes its a  pursuit towards once objectives or relentless pursuit towards desires. But reality is you are following what you think will make you  happy and every one does. That's when I stumbled upon this strange equation.

Now lets see what is the ingredient of happiness thru this equation.

 Happiness Index = No of desires fulfilled / No of desires pursued.

This one I noted down from a a book Self-Unfoldment by Chinmaya publications, and the book is quoting from vedanta which is a pre-historic Hindu  religious ideology of thought. The immediate thing I wanted to do was to find out the math in this equation and to find out if there is a scope for algorithmic treatment to this equation.Does looping this equation under a loop algorithm create lot of happiness ?. Does this could be made scale-able or is it good enough to try a iterative approach to make it contagious to make everyone happy.

Lets examine the boundary cases by giving numerator and denominator with values as infinity, zero, positive - negative numbers etc.

Case One: Numerator(positive\negative number) Denominator (positive\negative number): Lets examine the normal case for most of the individuals. This will be some positive or negative  number at Numerator and Denominator. Your happiness will be more if the numerator in the above equation increases . If the denominator decreases then too the happiness index increases.

Case Two: Numerator(zero) Denominator (positive\negative number): If the numerator is zero and denominator is non zero number, again your happiness will be zero. So its important that you try to create some value to be seen in the numerator and that could become the basis of your happiness if  you are not able to achieve infinite happiness(like explained below)

Case Three : Numerator( positive\negative number ) and Denominator (zero) : Denominator becoming zero is also a problem since division by zero (http://en.wikipedia.org/wiki/Division_by_zero) is undefined and your happiness will also be undefined.

 But this case seem to be curious to me that I tried to further drill down . Because my conscience was not allowing me to think that if I don't have a desire to pursue why cannot I be happy. For example if you see animals, animals had got enough rational thought to pursue a desire per se, rather there response is always instantaneous not to be treated as a desire, but still animals show moods of happiness and sadness. But if you check division by zero the calculus way, you could see that it seems possible to define a/0 by considering the limit of a/b as b approaches 0. :










This means, say if b is approaching to zero from positive number side then the answer could be treated as positive infinity. Meaning if you are in a state where your desires pursued are approaching zero but not zero then you will have this happiness index of positive infinity. I don't know yet to correlate positive infinity to something which someone have experienced, but it seems very intriguing to know. Is it something so sublime or is it the enlightenment Or is it the real heaven ?. Buddhist believe that Gautham Buddha had enlightenment. He was a prince and he decided to pursue a life without desires after enlightenment at  Bhod Gaya.

Now if the b was approaching to zero from the negative number side then the answer could be treated as negative infinity. What does negative value of not having a desire to pursue mean ? Is that pursuing others  not pursue any desire or is it a state where it needs lot of energy to have desires ? But moving from such a state to "zero desires to pursue" results in negative infinity. What does that correlate to ? Is this "hell"  ?

Case Four : Numerator( zero ) and Denominator (zero) : Again a undefined case. But it seems this case if often termed as infinity. Does that mean the happiness index will stand at a point where ones happiness is always infinite. Now in this case as above there is no scope of positive or negative infinity, does that mean this is the safest route to pursue happiness without having the risk of falling into negative or positive infinity (by whatever good or bad definitions positive or negative infinity translate too)

Anyway applying deterministic equations and algorithms to discrete science and thoughts is always intriguing and pure fun.

Sorting - A Quicksort Inplace algorithm in Python

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n . Before discussing about the in-place version lets see how its implemented without in-place rearrangements. Here is one such implementation below:

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n^2)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (log n) (for in-place)

The above algorithm uses two new arrays for its implementation and thereby does a bad job with regard to space complexity. Here is an inplace quicksort algorithm implementation in Python

If you are interested in a C implementation of the below algorithm see the following link: C implementation of inplace Quicksort.

Quicksort Inplace algorithm in C

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n^2)
Best Case Performance	O (n log n)
Average Case Performance	O(n log n)
Worst Case space Complexity		O (log n) (for in-place)

There are implementations of Quicksort algorithm using new new array creation and thereby does a bad job with regard to space complexity. Here is an inplace quicksort algorithm implementation in C. If you are interested in the implementation in python please click the following link: Python implementation of inplace quicksort

Printing level order algorithim

Two types of search are popular in Binary Tree. Breadth First Search (BFS) and Depth First Search (DFS) . Printing the level order is slightly complex since you need to keep track of the height of the particular node to implement the level order printing. Its a kind of BFS node tracking using the height.
Here is a c implementation of printing level order for a Binary Tree.

Binary Tree - Depth First Search Algorithm

Here is a Binary Tree search algorithm implementation in C for Depth First Search algorithm. The preOrder , inOrder and postOrder implementation are done thru recursive call approach.

BubbleSort algorithm in python

Although Bubblesort algorithm is not an efficient one with respect to space and time complexity, its one of the easiest one to understand. Here is a bubblesort implementation in python

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you would like to see how this implentation would look like in C click the following link: Bubblesort implementation in C

Quicksort inplace algorithm in Java

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n . Before discussing about the in-place version lets see how its implemented without in-place rearrangements. Here is one such implementation below:

Asymptotic Complexity
Time Complexity	Space Complexity
n log(n)	1

If you are interested in a C implementation of the below algorithm see the following link: C implementation of inplace Quicksort.

If you are interested in the implementation in python please click the following link: Python implementation of inplace quicksort

Insertion Sort in Python

Here is an implementation of Insertion sort in python.

Here we take the first element compare with zeroth element and swap values if the zeroth element is bigger. Now we take the second element. Compare with first one swap values if first one is bigger. Then again we compare the first value again with zeroth and swap if zeroth value is bigger. Like that
we do till end of the array.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	Swaps: O (n^2) Comparisons : O(n^2)
Best Case Performance	Swaps: O (1 ) Comparisons : O(n)
Average Case Performance	Swaps: O(n^2) Comparisons : O(n^2)
Worst Case space Complexity		Total: O (n) Auxiliary : O(1)

MergeSort Algorithm in Java

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example its a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly , since in Quicksort elements to be accessed randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n)
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

Bubblesort algorithm implementation in C

Here is a bubblesort implementation in C. Although bubblesort is not a efficient algorithm, its a simple algorithm to demonstrate what is a sorting algorithm

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you want to see the same implementation in python please click the following link: Bubblesort implementation in python

Bubblesort algorithm in Java

Given below is the Bubblesort algorithm in Java. Although bubblesort is not a efficient algorithm, its a simple algorithm to demonstrate what is a sorting algorithm

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you want to see the same implementation in python please click the following link: Bubblesort implementation in python

If you would like to see how this implentation would look like in C click the following link: Bubblesort implementation in C