Skip to content

Instantly share code, notes, and snippets.

@rdbuf
Last active August 31, 2017 02:29
Show Gist options
  • Save rdbuf/77dc8baaf2332da03925c4f1dacd8dbf to your computer and use it in GitHub Desktop.
Save rdbuf/77dc8baaf2332da03925c4f1dacd8dbf to your computer and use it in GitHub Desktop.
A more efficient mergesort implementation in Haskell
#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
using elem_t = uint64_t;
std::list<elem_t> msort(std::vector<elem_t>::iterator begin, std::vector<elem_t>::iterator end) {
if (end - begin == 1) {
return std::list<elem_t>(begin, end);
}
std::list<elem_t> list;
auto s1 = msort(begin, begin + (end - begin) / 2);
auto s2 = msort(begin + (end - begin) / 2, end);
s1.merge(s2);
return s1;
}
int main() {
std::vector<elem_t> a;
std::copy(std::istream_iterator<elem_t>(std::cin), std::istream_iterator<elem_t>(), back_inserter(a));
auto res = msort(a.begin(), a.end());
std::copy(res.begin(), res.end(), std::ostream_iterator<elem_t>(std::cout, ", "));
}
import Data.List.Utils (merge)
import Data.List.Split (chunksOf)
import Control.Monad (join)
import Control.Arrow -- (***)
import Data.List (sort)
import Data.Vector
msort :: Ord t => Vector t -> [t]
msort vec | Data.Vector.length vec > 1 = uncurry merge $ join (***) msort $ Data.Vector.splitAt (ceiling $ fromIntegral (Data.Vector.length vec) / 2) vec
| otherwise = toList vec
main :: IO ()
main = do
dat <- getLine >>= return . fromList . Prelude.map read . words :: IO (Vector Int)
let sorted = msort dat
print sorted
return ()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment