0

I thought of a sorting algorithm but I am not sure if this already exists.

Say we have a container with n items:

We choose the 3rd element and do a binary search on the first 2, putting it in the correct position. The first 3 items in the container are sorted.

We choose the 4th element and do a binary search on the first 3 and put it in the correct position. Now the first 4 items are sorted.

We choose the 5th element and do a binary search on the first 4 items and put it in the correct position. Now 5 items are sorted.

. . .

We choose the nth element and do a binary search on the other n-1 elements putting it in the correct position. All the items are sorted.

Binary search takes logk for k elements and let's say that the insertion takes constant time. Shouldn't this take:

log2 to put the 3rd element in the correct spot. log3 to put the 4th element in the correct spot. log4 to put the 5th element in the correct spot. . . . log(n-1) to put the nth element in the correct spot.

log2 + log3 + log4 + ... log(n-1) = log((n-1)!) ?

I may be talking nonsense but this looked interesting.

EDIT:

I did not take the insertion time into consideration. What if the sorting was done in a sorting array with gaps between the elements? This would allow for fast inserting without having to shift many elements. After a number of inserts, we could redistribute the elements. Considering that the array is not sorted (we could use a shuffle to ensure this) I think that the results could be quite fast.

Improve this question
11
  • binary search is not a sort. But if I understand what you're trying to describe it sounds similar to a bubble sort. I think your log(n-1) is off. Commented Apr 8, 2014 at 20:50
  • we use binary search to find the correct position to put the item in the sorted part of the container. Commented Apr 8, 2014 at 20:51
  • 2
    The problem is that you can't just find where it goes, you have to move all the other stuff out of the way. Essentially that makes this insertion sort. Commented Apr 8, 2014 at 20:52
  • 2
    I think by binary search, he meant that there is an insertion taking place placed on a searchable index of where we would expect to find the item we are inserting. in which case it would be called insertion sort... Either way it's still N*log(N) Commented Apr 8, 2014 at 20:53
  • 1
    First issue is that log(A) + log(B) = log(A*B) not log(A+B), making it O(log(N!)) which is O(N log N). I do believe you are basically adding elements to a binary search tree. It would require O(log N) to add the element and O(log N). That is the best way to avoid O(N) for the insertion cost and still maintain the order. Commented Apr 8, 2014 at 20:53

3 Answers 3

Reset to default
4

It sounds like insertion sort modified to use binary search. It's fairly well-known, but not particularly well-used (as far as I know), possibly because it doesn't affect the O(n²) worst case, but makes the O(n) best case take O(n log n) instead, and because insertion sort isn't commonly used on anything but really small arrays or those already sorted or nearly sorted.

The problem is that you can't really insert in O(1). Random-access insert into an array takes O(n), which is of course what the well-known O(n²) complexity of insertion sort assumes.

One could consider a data structure like a binary search tree, which has O(log n) insert - it's not O(1), but we still end up with an O(n log n) algorithm.

Oh O(log (n!)) = O(n log n), in case you were wondering about that.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Insertion sort is used as part of Timsort, hybrid sorting algorithm implemented as standard in Java and Phyton, since it's very effective for partially sorted data.
heap sort is still O(n log n)... It says that on the top of the wiki page you just referenced. typo maybe? It's been too long for me, were you referencing the best case scenario?
heapsort is O(n log n) in the best and worst cases
@RustyWeber I actually meant using a BST. I removed my mention of heapsort, so I'm not sure of the exact phrasing I used, but I know heapsort is O(n log n).
@Veritas: No, you'd need to use a self-balancing tree to avoid O(N^2) worst case.
|
3

Tree sort (generic binary search tree) and splaysort (splay tree) both use binary search trees to sort. Adding elements to a balanced binary search tree is equivalent to doing a binary search to find where to add the elements then some tree operations to keep the tree balanced. Without a tree of some type, this becomes insertion sort as others have mentioned.

In the worst case the tree can become highly unbalanced, resulting in O(N^2) for tree sort. Using a self-balancing binary search tree yields O(N log N), at least on average. Splay sort is an adaptive sort, making it rather efficient when the input is already nearly sorted.

Improve this answer

Comments

1

I think by binary search, he meant that there is an insertion taking place placed on a searchable index of where we would expect to find the item we are inserting. in which case it would be called insertion sort... Either way it's still N*log(N)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.