Sorting Algorithm analysis on a list of 0 and 1 element. I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only.
a) Heapsort
b) Quicksort
c) MergeSort
d) Insertion Sort.
I'm looking for difference in number of comparison required for sorting the list. 
Exact Question: How the restriction of 0's and 1's element may affect the total number of comparison done and give the resulting \theta bound. In my perspective there won't be any change in MergeSort and Insertion sort as they would require the same number of comparison.
However on a very different thought, I'm thinking that if we know about the data (i.e. they are 0 or 1) then in decision tree there won't be n! factorial outputs. As we can reduce it to few less I'm not sure about this decision tree thought. Please provide your thoughts on this.
 A: Mergesort is an oblivious algorithm, which is to say that it will perform the same steps (except for those involved in merging) for each input sequence, so its average-and worst-case times will be $\Theta(n\log n)$ on inputs restricted to $0/1$ sequences.
Insertion sort becomes interesting for your inputs, but it's not too hard to see that the worst-case running time will still be $O(n^2)$: Look at the number of swaps that will have to be done on the input $\langle\; 1, 0, 1, 0, \dots , 1, 0\;\rangle$. The average performance is, as usual, more involved and I'm not ready to claim any results for that.
Quicksort is even more interesting, since the first call to partition will leave the array in sorted order after $O(n)$ swaps. If QS were written with that in mind, then its behavior would change from $O(n\log n)$ on average (or $O(n^2)$ in the worst case) to $O(n)$. If this fact weren't identified, then after the first partition, the subsequent ones would split each subarray into two pieces, one containing a single element and the other containing all the rest, leading to $O(n^2)$ performance in both average- and worst-case. 
Oops! I just noticed that heapsort was also on your list. I'll have to get back to you on that.
A: Best case = data already sorted
Average case= some data sorted, some data unsorted.
Worst case= data totally unsorted
Merge sort: Best = NlogN , AVE=NlogN,  WORST = NlogN
Insertion Sort = Best = N , AVE=N^2,  WORST = N^2
Quicksort = NlogN , AVE=NlogN,  WORST = N^2
