Created
May 29, 2017 07:39
-
-
Save Bennyelg/da85a34c535f16d94633f494ed4720c4 to your computer and use it in GitHub Desktop.
merge_sort implementation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import strutils | |
import math | |
#[ | |
Module name: Implementation of MergeSort recursion. | |
Author: Benny E. | |
Mail: elgazarbenny at gmail.com | |
]# | |
proc merge(left: seq[int], right: seq[int]): seq[int] = | |
var | |
list: seq[int] | |
i = 0 | |
j = 0 | |
list = @[] | |
while list.len < (left.len + right.len): | |
if left[i] < right[j]: | |
list.add(left[i]) | |
i += 1 | |
else: | |
list.add(right[j]) | |
j += 1 | |
if i == left.len or j == right.len: | |
if i == left.len: | |
list.add(right[j..right.len - 1]) | |
if j == right.len: | |
list.add(left[i..left.len - 1]) | |
break | |
return list | |
proc MergeSort*(s: seq[int]): seq[int] = | |
if s.len < 2: | |
return s | |
var firstHalf = MergeSort(s[0..int(floor((s.len) / 2) - 1)]) | |
var secondHalf = MergeSort(s[int(floor((s.len) / 2))..(s.len - 1)]) | |
return merge(firstHalf, secondHalf) | |
discard MergeSort(@[7,48, 19, 9, 90]) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment