# 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.

-
Side note: Counting sort would sort such an array in $O(n)$. en.wikipedia.org/wiki/Counting_sort –  Ayman Hourieh Sep 27 '12 at 0:35
Have you considered asking this on the computerScience.SE beta site? –  Rick Decker Sep 27 '12 at 18:47
Nopes, I'm not aware of this website. Can you give me exact url? (computerScience.se doesn't load) –  Rohit Kandhal Sep 27 '12 at 18:54

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.

-
Thanks for your response. :) I too got somewhat similar result but wasn't sure whether they are correct or not. Here are my results: Insertion Sort: theta(n^2), If either no. of 1's or 0's are constant then it is theta(n) Merge Sort: theta(nlogn), No change even if 1's or 0's are constant. Heapsort: theta(nlogn), If no. of 1's are constant then theta(nlogn). If no. of 0's are constant then theta(n). QUickSort: theta(n^2), No change if no. of 0's or 1's are constant. –  Rohit Kandhal Sep 27 '12 at 18:51

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

-
I know about these formulas, I want to know what difference would it make with the input values between 0 and 1 only. Would there be any change theta bound of these algo? I think there will be some but I'm not able to figure out the appropriate way to findout the same. –  Rohit Kandhal Sep 27 '12 at 5:18