Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
7
votes
4answers
518 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 ...
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: ...
25
votes
1answer
2k views

Merge sort in Scheme

...
5
votes
2answers
391 views

Modern, C++ compliant, merge sort

This is a kind of follow up to my previous sort implementation review with specific questions to merge sort, and Modern C++ idioms. ...
5
votes
3answers
2k views

Natural merge sort

Note: the next iteration at Natural merge sort - follow-up I have compiled natural merge sort algorithm from Java to C++. Natural merge sort sacrifices at most \$2N\$ amount of work in order to ...
4
votes
1answer
1k views

Natural mergesort

This is a problem from Robert Sedgwick's Algorithms book: Write a version of bottom-up mergesort that takes advantage of order in the array by proceeding as follows each time it needs to find two ...
3
votes
2answers
295 views

Implementation of the merge_sort - comparing the timing of an array versus a vector

I'm going through the book Introduction to Algorithms. I made a comparison between merge-sort for an array of integers versus a vector. Could I have structured this program better? Why is the ...
1
vote
0answers
173 views

Natural merge sort in Java - follow-up 2

See the the previous iteration. Now I refactored the code a bit so that I do not need to pass like 6 parameters to helper methods. Also, I did a small tweak that allows the sort to arrive to the ...
30
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. ...
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 ...
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? ...
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 ...
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 ...
5
votes
2answers
118 views

Classic merge sort

Here is my code for classic merge sort. My question is, each time I create a new list result to merge sub-parts, is there a way to save the space -- not creating a ...
2
votes
1answer
646 views

Implementation of Merge Sort in C++

I'd originally not copied the result vector to vec which I figured and corrected. Iis there a better way to implement the merge sort other than the approach I've taken? ...
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\$ ...
7
votes
3answers
1k views

Merge Sort implemented using iterators

...
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 ...
5
votes
2answers
995 views

ANSI C Mergesort

This is a working mergesort implementation I wrote as I'm trying to get back into C. I am not so much interested in feedback on the optimality of the algorithm (as I could read up countless articles ...
5
votes
1answer
13k views

Merge Sort in C++

I've written this code for a merge sort, which is meant to implement the pseudo-code from Cormen's Introduction to Algorithms: ...
3
votes
3answers
728 views

Merge Sorting in Python

This my implementation of the Merge Sorting Algorithm: ...
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 ...
10
votes
1answer
904 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, ...
6
votes
1answer
243 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
1answer
309 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 ...
5
votes
3answers
116 views

Java merge sort implementation

Is this a good implementation? ...
4
votes
3answers
183 views

Mergesort performance in C

I have two questions about my code: Are there any performance improvements in this implementation or generally (register int ?) that I could make? What could I ...
4
votes
4answers
439 views

Implementation of mergesort in C

I have implemented mergesort in C. Any advice on making it more compact? My merge function seems less than fully optimal. ...
2
votes
1answer
803 views

Natural merge sort in Java - follow-up

See the previous iteration: Natural merge sort in Java See the next iteration: Natural merge sort in Java - follow-up 2 Arrays.java ...
2
votes
1answer
117 views

Adaptive Mergesort in Java - follow-up

(See the previous and first iteration.) Adaptive Mergesort This algorithm is from a paper "Sublinear Merging and Natural Mergesort" by Svante Carlsson, Christos Levcopoulos and Ola Petersson. It ...
2
votes
2answers
2k views

Merge sort algorithm implementation using C++ (redux)

This is a follow up question to the one I asked a couple of days ago. I reviewed the suggestions & did some research (specifically, read relevant info on CLRS). The new version is 3 times faster (...
0
votes
2answers
411 views

Merge sorting a singly-linked list in C

(See the next iteration.) I have this C implementation of the merge sort for sorting singly-linked lists: ...
8
votes
1answer
371 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 ...
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: ...
4
votes
1answer
205 views

Natural merge: mergesort that uses already sorted subarrays

The code bellow is my implementation for the natural merge exercise in Robert Sedgwick's Algorithms book: Write a version of bottom-up mergesort that takes advantage of order in the array by ...
4
votes
3answers
351 views

C++ Merge Sort Implementation - Pt2

Following the review of my old merge sort implementation here, it appears that the biggest improvement to make was to use iterators instead of copying the vectors. ...
3
votes
2answers
289 views

Merge two sorted lists in Python

Merge two sorted lists ...
3
votes
1answer
2k views

Natural merge sort in Java

Natural merge sort is a modification of merge sort that sacrifices \$\mathcal{O}(N)\$ to actually build a list of "runs" that may be defined as monotonically increasing or strictly decreasing ...
3
votes
1answer
310 views

Adaptive Mergesort in Java

(See the next iteration.) This natural merge sort here is from "Sublinear Merging and Natural Mergesort" by Svante Carlsson, Christos Levcopoulos and Ola Petersson. The funky part is that it may ...
3
votes
3answers
361 views

Merge sorting a singly-linked list in C - follow-up

(See the initial iteration.) Continuing from Merge sorting a singly-linked list in C, I have incorporated the points made by @vnp. Now it looks like this: ...
3
votes
1answer
223 views

Implement the merge sort + binary search algorithms to filter and merge sort two arrays

I wanted to take my own shot at a merge sort array implementation. I took on the prompt from Rahul's post. The goal (altered a little for my purposes): Implement a solution capable of merging &...
3
votes
2answers
654 views

Merge sorting a singly-linked list in Java

I have this nifty merge sort implementation for sorting singly-linked lists. Its running time is \$\Theta(n \log n)\$, yet it uses only \$\Theta(\log n)\$ space (the stack). See what I have below. ...
2
votes
1answer
67 views

If given two sorted arrays where first containing -1, merge into one sorted array

If given two arrays arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1] arrayTwo = [1,10,17,56] Both the array's are sorted but array1 consists -1 in between the ...
2
votes
1answer
346 views

Mergesort algorithm in C

I have this mergesort implementation that has exactly the same API as qsort: mergesort.h: ...
2
votes
3answers
578 views

Natural merge sort in C

I have this C implementation of the natural merge sort: ...
1
vote
0answers
72 views

Mergesorting a stack in Java - a new algorithm

(See the previous iteration.) Now I have implemented a stack merge sort that does not have to reverse every substack after sorting it, and it allocates the two auxiliary stacks only once prior to the ...
1
vote
1answer
135 views

Mergesorting a stack in Java

(See the next iteration.) I have this small program for sorting a stack using mergesort. Basically, the aim was to use as little aid from JDK library as possible. See what I have: StackMergesort....