Number of comparisons using merge sort

Question

If you have 5 different numbers, how many comparisons do you need to sort using merge sort?

Answer 1

I find the question interesting, so I decided to study it completely (with a little experiment in Python).

I downloaded mergesort.pyfrom here and modified it to add an argument cmpto the comparator function. Then:

import collections
import itertools
import mergesort
import sys

class CountingComparator(object):
  def __init__(self):
    self.count = 0
  def __call__(self, a, b):
    self.count += 1
    return cmp(a, b)

ms_histo = collections.defaultdict(int)

for perm in itertools.permutations(range(int(sys.argv[1]))):
  cc = CountingComparator()
  lperm = list(perm)
  mergesort.mergesort(lperm, cmp=cc)
  ms_histo[cc.count] += 1

for c in sorted(ms_histo):
  print "%d %2d" % (c, ms_histo[c])

The resulting simple histogram (starting from length 4, as in the case of its development and debugging):

4  8
5 16

For the problem, as indicated, with a length of 5 instead of 4, I get:

5  4
6 20
7 48
8 48

and length 6 (and wider format ;-):

7    8
8   56
9  176
10 288
11 192

Finally, length 7 (and even wider format ;-):

 9   16
10  128
11  480
12 1216
13 1920
14 1280

, - , , , . - ?

Answer 2

, [0,1,2,3,4]?

Answer 3

- L1 L2 , - L1 + L2-1.

• 1- .
• 2 , 2,2 1.
• 2 1 1 + 2-1 = 2 , 2 3 .
• , 2 + 3-1 = 4 .

, , 8.

: [2], [4], [1], [3], [5] → [2,4], [1,3], [5] → [2,4], [1,3,5 ] → [1,2,3,4,5]

Edit:

Erlang. , 5,6,7 8 1,5.

-module(mergesort).

-compile(export_all).


test() ->
  lists:sort([{sort(L),L} || L <- permutations()]).

sort([]) -> {0, []};
sort([_] = L) -> {0, L};
sort(L) -> 
  {L1, L2} = lists:split(length(L) div 2, L),
  {C1, SL1} = sort(L1), {C2, SL2} = sort(L2),
  {C3, RL} = merge(SL1, SL2, [], 0),
  {C1+C2+C3, RL}.

merge([], L2, Merged, Comps) -> {Comps, Merged ++ L2};
merge(L1, [], Merged, Comps) -> {Comps, Merged ++ L1};
merge([H1|T1], [H2|_] = L2, Merged, Comps) when H1 < H2 -> merge(T1, L2, Merged ++[H1], Comps + 1);
merge(L1, [H2|T2], Merged, Comps) -> merge(L1, T2, Merged ++[H2], Comps + 1).


permutations() ->
  L = lists:seq(1,5),
  [[A,B,C,D,E] || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A =/= E, B =/= C, B =/= D, B =/= E, C =/= D, C =/= E, D =/= E].

Answer 4

http://www.sorting-algorithms.com/

Answer 5

Wikipedia: , , (n ⌈ lg n⌉ - 2 ^ ⌈lg n⌉ + 1)

Answer 6

, , 8, - 7. : -

, a, b, c, d, e

: a, b, c d, e

: a, b & c d & e

: a & b c d & e

, -

a b: a, b

a, b c: a, b, c

d e: d, e

a, b, c d, e: id d a, b, c, d, e

, , - .