Comparing sorting algorithms -- Insertion Sort vs. Merge Sort

  • Thread starter r0bHadz
  • Start date
  • #1
194
17

Homework Statement:

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in [itex]54n \log_2n [/itex] steps. For which values of n does insertion sort beat merge sort?

Relevant Equations:

2^(n/8) < n
The answer says insertion sort runs faster when we're sorting less than 43 items. I agree but with the condition that the first item will not be faster. Why does the answer not mention this? Is it because it is insignificantly faster?
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,622
952
It is because sorting a list of 1 item is a no-op and is usually not interesting.
Still, it should have mentioned that exception.
 
  • Like
Likes berkeman
  • #3
rcgldr
Homework Helper
8,707
534
Comparing 8 n^2 versus 54 n ceiling(log2(n)) the change occurs between n = 40 and n = 41.
ceiling log2(n) = 6, for n from 33 to 64 inclusive.
8 · (40^2) = 12800 versus 54 · 40 · 6 = 12960
8 · (41^2) = 13448 versus 54 · 41 · 6 = 13284
 
Last edited:

Related Threads on Comparing sorting algorithms -- Insertion Sort vs. Merge Sort

  • Last Post
Replies
1
Views
2K
Replies
0
Views
2K
Replies
14
Views
13K
  • Last Post
Replies
0
Views
5K
Replies
7
Views
3K
Replies
1
Views
5K
Replies
12
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
6
Views
6K
Top