Questions tagged [mergesort]

Merge sort is an O(n log n) comparison-based sorting algorithm.

Filter by
Sorted by
Tagged with
31
votes
10answers
14k views

Sorting large 1GB file with 100 millions numbers using merge sort

My task is to sort 1GB file with 100 million numbers using merge sort without recursion. My idea is to split file into 4 pieces, then to 2 and at the end to one file. ...
25
votes
1answer
2k views

Merge sort in Scheme

...
14
votes
2answers
8k views

Parallel Merge Sort

Parallism is achieved by using a simple call to tbb::parallel_invoke(). However I can't break a speedup factor of x2 (after ~3-4 parallel HW threads), although 8 ...
12
votes
4answers
41k views

Merge Sort an integer array

I've implemented merge sort an integer array. Is it okay to use i,j,k as variable name for looping? Should I change them to more meaningful names? Overall, any further suggestions on this code? ...
10
votes
7answers
2k views

Merge sort for a List<T>

Is this merge sort following good coding standards? What are some improvements I can make to make it cleaner? ...
10
votes
5answers
6k views

Merge two already sorted linked list

This is code to merge two sorted linked lists. l1 and l2 are sorted. While calling the merge function via ...
10
votes
4answers
3k views

Merge sort C# Implementation

Its been years (10+) since I have worked with sorting algorithms directly. So I have been trying to go over them again to refresh my memory. The thing is my ideas of how to do it doesn't seam to ...
10
votes
1answer
902 views

File-based fixed-record merge sort

A problem posted here to Code Review prompted me to experiment with a general-purpose merge-sort algorithm for any fixed-length record data. External / File-based mergesort I answered that question, ...
9
votes
4answers
2k views

C++ Merge Sort Implementation

Edit: A follow up question can be found here. My first try at mergesort, without resorting to any references: ...
9
votes
2answers
2k views

Merge sort using sentinels

This is my implementation of recursive merge sort, using sentinels: ...
8
votes
3answers
23k views

Merge sort algorithm implementation using C++

I'm trying to learn proper C++ and algorithms at the same time. I particularly feel weird about my iterators usage in merge function. Is this a good way to handle ...
8
votes
5answers
19k views

Merge Sort Algorithm in Python

I'm implementing basic sorting algorithms to learn them, and coding, better. Criticisms and possible optimizations welcome. ...
8
votes
1answer
4k views

Merge sort in Scala

I've implemented merge sort in Scala: ...
8
votes
4answers
3k views

Given two sorted arrays, add the elements of the second array into the first

In Cracking the Coding Interview by Gayle Laakmann McDowell, there's a question that asks you to write code for the following: Given two sorted arrays, A and B. Write a method merging the elements ...
8
votes
1answer
17k views

Inversion count using merge sort

...
8
votes
1answer
1k views

Generic Template implementation of merge sort in C++

A few month ago I wrote several basic sort algorithm for educational purposes as generic as possible in C++. In a few days time I want to present some of that stuff in my class but before that I ...
8
votes
1answer
360 views

Constructing an odd-even mergesort sorting network

I was searching for a non-recursive odd-even mergesort implementation and found this one: Sedgewick R. The resulting sorting network is not an odd-even-merge sort network. When one draws a diagram ...
8
votes
2answers
2k views

String merge sort in Java

This snippet is about sorting a set of strings using merge sort. However, this version is tailored for strings as it relies on lcp values: Given two strings \$A\$ ...
8
votes
0answers
46 views

Parallel merge sort with thread- and bufferpooling

I did wrote this parallel merge sort with no external dependencies. I tried to make use of modern C++ as much as possible. Can you please tell me how it is? ...
7
votes
4answers
517 views

MergeSort performance

Do you see any inefficient parts with the following code? On internet I see 30 ms for 100.000 integers but I can sort 100.000 integers in 300ms. The data is random. I am using late 2013 macbook pro so ...
7
votes
3answers
1k views

Merge Sort implemented using iterators

...
7
votes
4answers
1k views

Merging two files containing sorted numbers into one

The task is to merge 2 text files containing sorted integers into one file. Each number in both files is stored in new line(there are no empty lines,and only numbers are stored). Requirements are that ...
7
votes
3answers
757 views

Is this attempt at a merge sort correct?

I am trying to write a merge sort algorithm. I can't tell if this is actually a canonical merge sort. If I knew how to calculate the runtime I would give that a go. Does anyone have any pointers? <...
7
votes
3answers
12k views

Merge sort implementation with vectors

I'm new to algorithms. To be honest I am not really sure if my implementation is right. However, the output is sorted correctly in ascending order so perhaps it's correct. Please feel free to give ...
7
votes
2answers
1k views

MergeSort in Rust

I've just started learning Rust and put together this working MergeSort implementation. Wondering what I've overlooked and what I could improve. I couldn't figure out a cleaner way to deal with the <...
7
votes
2answers
7k views

External / File-based mergesort

I've implemented an external mergesort to sort a file consisting of Java int primitives, however it is horribly slow (fortunately it does at least work). Very little happens in the sort method: it ...
7
votes
1answer
705 views

Merge sort and selection sort comparison taking too long

I have this python code that compares merge sort and selection sort, but it is taking "forever." ...
7
votes
3answers
2k views

Merge Sort in Perl

I'm new to Perl and have successfully written a merge sort program. I'll paste the entire program below, but would like mostly a review of the subroutines ...
7
votes
2answers
3k views

Is this non-recursive mergesort efficient and a good way to simulate the recursive version?

My teacher assigned us to do the recursive version of mergesort, yet I heard that the non-recursive version (bottom up) is a bit tougher, so I decided to this one as well. My main concerns are: ...
7
votes
2answers
2k views

Merge sort in JavaScript

I implemented this merge sort in JS and noticed that for random integer numbers it's a lot faster than the build in sort functions of all the browsers I tested (Chrome, FF, IE). Does anyone have an ...
7
votes
1answer
249 views

Functional K-way merge (Merge k sorted sequences)

I've implemented a functional k way-merge algorithm to merge k sorted sequences of any type T. I used scalaz's Heap since the Scala standard library does not provide an immutable heap. Any suggestions ...
7
votes
2answers
836 views

Merge Sort without pointers in C

As part of an online course exercise, I was supposed to implement Merge Sort in C. Pointers were still not discussed prior to this exercise, so I have to work with arrays. Memory efficiency is not ...
6
votes
4answers
959 views

Generic merge sort in C++ using a user-defined comparison function or the < operator by default

I wanted to implement a generic merge sort algorithm using the same interface as std::sort(). The interface takes first and last iterators to a range of elements in ...
6
votes
5answers
2k views

Merge two sorted lists of numbers

Inputs are two sorted lists (of the same length) of numbers. I would like to return a new merged, sorted new list. I have written the following code, but most lines are used to deal with the end case. ...
6
votes
2answers
1k views

Merge Sorting Lists

I'm fairly new to Java, arriving in the "future" from C and returning to type safety from Python. I'm looking for your suggestions to improve this code in the following areas: Correctness - are there ...
6
votes
4answers
15k views

Merge two list and discarding duplicates

I am trying to implement a function that merges two ordered lists into a third (ordered) one, but duplicates have to be discarded (basically the last step of a mergesort). I think that this code can ...
6
votes
5answers
2k views

Takes in two sorted lists and outputs a sorted list that is their union

Write a function that takes in two sorted lists and outputs a sorted list that is their union Could anyone help me to improve this code and make it more user-friendly? We are not supposed to use ...
6
votes
2answers
564 views

C++ parallel merge sort

I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This ...
6
votes
1answer
13k views

Recursive merge sort in python

I'm very new to python, however not new to programming as I've been doing C for some time. So here is my practice of a merge sort, I looked at other questions however they were many more lines ...
6
votes
2answers
1k views

Implementation of merge sort algorithm in C++

This is my implementation of "merge sort" in C++. I'm still a newbie at C++ so: Have I understood how merge sort works and implemented it in the right way? Have I used any bad practices? How could ...
6
votes
2answers
10k views

Merge sorting linked lists

This works as expected and I want to get this code reviewed so that I can improve my coding ability. I am concerned about readability and the quality of the code ...
6
votes
1answer
236 views

Natural merge sort - follow-up

The previous iteration at Natural merge sort Now my code relies on C++14 and looks like: natural_merge_sort.h: ...
6
votes
2answers
3k views

Merge sort in C++ with iterators

I implemented merge sort with C++ and would like to get some feedback. ...
6
votes
1answer
217 views

Merge sort could work 10 times faster

I am implementing merge sort in Java and I have a performance problem in this method: ...
6
votes
1answer
101 views

Merge sort practice

Never written a merge sort for huge files before. So after this mornings question I though I would give it a go. ...
6
votes
1answer
10k views

Counting inversions

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion ...
6
votes
1answer
307 views

Recursive implementation of merge sort

Information about my code: I am following this MIT OCW algorithms course. The first lecture described insertion sort and merge sort. I implemented merge sort in C. The algorithm is structured as a ...
6
votes
2answers
1k views

Merge Sort: exercise

I've decided to learn Haskell by following the current Coursera algorithms course using Haskell to implement the algorithms discussed. First up is merge sort, which I've implemented as shown here. I'...
6
votes
3answers
227 views

Merge Sort implementation in Java

Can you check my merge sort implementation? From all of my testing it seems like it works, but I just wanted to make sure I am doing it as good as possible, and it couldn't be optimized any further. ...
6
votes
1answer
339 views

Algorithm for finding inversions in Merge Sort

Please help in code reviews for readability, optimizing it, functionality etc. ...