search

scozv / algo-js

[obsoleted] has been moved to project Tango:
https://github.com/scozv/tango
GNU General Public License v3.0
2 stars 1 forks source link

bad performance of merge sort #1

Closed scozv closed 10 years ago

scozv commented 10 years ago

From Algo.js of Google Code on July 15, 2013 10:14:07

What steps will reproduce the problem?

  1. merge sort an array containing 100000 elements
  2. sort seems to be very slow What is the expected output?

What do you see instead? merge sort should be finished in less than five seconds, at least. no output after one minute.

What version of the product are you using? On what operating system? it doesn't matter.

Please provide any additional information below. nothing else.

Original issue: http://code.google.com/p/algo-js/issues/detail?id=1

scozv commented 10 years ago

From Algo.js of Google Code on July 14, 2013 19:26:50

I debugged merge sort in chrome, each time when I pause the process, the code stopped at the function named _deepCloneTo(arr, to).

It's my fault to copy arr to another deeply from 0 to len(arr) - 1, during each recursive merge. Then, the time of this version merge sort will be:

__(2^1 + 2^2 + 2^3 +...+2^(logn)) * n * logn ~ n^2 logn__

I have fixed this issue by deeply copy arr to another just during the merge segment.

Status: Fixed

scozv commented 10 years ago

From Algo.js of Google Code on July 14, 2013 19:47:52

This issue was closed by revision 9a51f571c7d6 .