codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
201 stars 267 forks source link

Add Merge Sort Algorithm #461

Closed youknowqyh closed 2 years ago

youknowqyh commented 2 years ago

References to other Issues or PRs or Relevant literature

Brief description of what is fixed or changed

A natural merge sort is similar to a bottom-up merge sort except that any naturally occurring runs (sorted sequences) in the input are exploited. Example:

Start : 3 4 2 1 7 5 8 9 0 6 Select runs : (3 4)(2)(1 7)(5 8 9)(0 6) Merge : (2 3 4)(1 5 7 8 9)(0 6) Merge : (1 2 3 4 5 7 8 9)(0 6) Merge : (0 1 2 3 4 5 6 7 8 9)

Other comments

REF LINK - https://en.wikipedia.org/wiki/Merge_sort

codecov[bot] commented 2 years ago

Codecov Report

Merging #461 (4ac683e) into master (c0d2786) will increase coverage by 0.005%. The diff coverage is 100.000%.

@@              Coverage Diff              @@
##            master      #461       +/-   ##
=============================================
+ Coverage   98.549%   98.554%   +0.005%     
=============================================
  Files           29        29               
  Lines         3792      3806       +14     
=============================================
+ Hits          3737      3751       +14     
  Misses          55        55               
Impacted Files Coverage Δ
pydatastructs/linear_data_structures/__init__.py 100.000% <ø> (ø)
pydatastructs/linear_data_structures/algorithms.py 99.773% <100.000%> (+0.007%) :arrow_up:

Impacted file tree graph

czgdp1807 commented 2 years ago

We already have merge_sort_parallel. Using one thread there will be equivalent to normal merge sort algorithm. Thanks for the PR though. Closing it now.