Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
655 views

Merge Sort Algorithm Python

I started implementing algorithms to learn them in order to get better at programming. Here is a merge sort one and criticisms / optimizations are welcome. ...
1
vote
0answers
221 views

Generic natural merge sort a linked-list in C

I have a .h file that implements my "generic" by defining LINK_* beforehand. This is an implementation of natural merge sort on doubly-linked lists using log n ...
2
votes
1answer
1k views

Multithreaded bottom up merge sort

Before I tried this, my impression was that (bottom up) merge sort would be memory (actual RAM) bound, and not affected much by multithreading, but a 4 thread sort is about 3.0 times as fast as a ...
4
votes
1answer
948 views

Merge sort in one Single Function in Scala

I have implemented a sortmerge in Scala in one single function. I would like to have it reviewed, so that I can have it well organized, and it is then doing what ...
1
vote
2answers
734 views

Merging K Sorted Arrays

My aim is to merge k different sorted array with unique elements and I want a code review about it, here is my code below which is written in java; ...
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 ...
1
vote
0answers
132 views

Merge sort in PHP - my first algorithmic exposure to PHP 5

I have this small program in PHP implementing merge sort. I used one rather simple run time optimisation via using one additional array which allows faster merge operations: ...
2
votes
1answer
638 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? ...
4
votes
1answer
1k views

Merge sort implementation in Python

...
1
vote
2answers
1k views

Merge sort using c++ vectors

I'm still learning C++ and also algorithms. So I'm expecting to do a lot of refactoring. Here's my code ...
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: ...
0
votes
2answers
409 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: ...
3
votes
2answers
379 views

C++ Mergesort Implementation

I am currently in the process of learning C++. As such, I am making small programs to get more comfortable with the language. One of these programs is a small mergesort function with a basic wrapper ...
4
votes
2answers
177 views

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

In this iteration, I incorporated all but one points made by forsvarir in the previous iteration. Now my code looks like this: LinkedListNode.java: ...
3
votes
2answers
653 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. ...
3
votes
2answers
5k views

Merge Two Sorted Linked Lists

I solved this problem in C++. I was having trouble though understanding what return headA; and return headB; returns after going back down the recursion tree. A code review is also appreciated! You’...
2
votes
1answer
316 views

Recursive Implementation of Merge Sort C++

I am currently reading an algorithms book and I read on the insertion and merge sorts. I implemented the merge sort in C++, The first function MERGE is responsible for the merging of the two subarrays ...
3
votes
0answers
160 views

Functional Merge Sort

I just finished this Merge Sort in Clojure, structured according to ex. 22-26 of this workshop. The main question I have can be answered without spending time understanding the code: ...
1
vote
1answer
59 views

merge sort implementation 7

Please look at the above code ...
3
votes
1answer
1k views

Sorting seems to be slower with 2 threads instead of 1

I'm implementing a simple merge sort to practice with Python's Threads. I've tried to split the job into two threads, that sort normally, then I can join them and merge the result. However, it takes ...
3
votes
2answers
195 views

SPOJ “It's a murder!” challenge

I wrote a solution for SPOJ "It's a murder!". I'm exceeding the time limit even after n log(n) solution and fast I/O. Given a list of numbers, I need to calculate the sum of the sum of the previously ...
2
votes
2answers
1k views

Merge sort Python implementation

Is this efficient? ...
4
votes
1answer
354 views

Bottom up (iterative) mergesort in C

I have this C implementation of the bottom-up (iterative) mergesort: mergesort.h: ...
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 ...
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 ...
2
votes
1answer
342 views

Mergesort algorithm in C

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

Memory/performance of merge sort code

I wrote up merge sort code for some late night snack. I have gotten it working, but was just looking learn if I was missing anything in terms of efficiency. Could this code be significantly improved ...
5
votes
3answers
241 views

Merging 3 sorted linked lists

I already know how to merge two linked list, but I needed to code a function that'll merge three already sorted linked lists into one. I wrote a code and it is working fine, it takes care of null ...
2
votes
2answers
1k views

Recurrent merge sort (without recursion)

For educational purpose I implement recurrent merge sort without recursion. The algorithm idea seems absolutely clear but my implementation appears to be really slow: 5 seconds to sort 10,000 values; ...
1
vote
0answers
71 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....
3
votes
1answer
127 views

How to make doubly linked list design more efficient?

I have played recently and implemented doubly linked list with merge sort algorithm. I was wondering if there is any way of improving the algorithm further to make it as fast as possible (I know about ...
5
votes
3answers
116 views

Java merge sort implementation

Is this a good implementation? ...
5
votes
1answer
420 views

Creating a count inversion array of an unsorted array of unique integers

Given an array: arr = [2,3,1,4] I could write a count inversion array such that counting all numbers n2 after a certain ...
3
votes
1answer
141 views

Merge sort implementation efficiency

I made a merge sort implementation in C++, which I have tested with the values: 6, 38, 27, 7, 12, 58, 92, 43, 3, 9, 82, 10 producing the correct output of: <...
2
votes
2answers
2k views

Simple Java mergeSort implementation

...
5
votes
1answer
6k views

Parallel merge sort in Java

I have rolled my own parallel merge sort. My performance figures are as follows: Seed: 1457521330571 java.util.Arrays.sort() in 6840 ms. Sorted: true java.util.Arrays.parallelSort() 3777 ms. Sorted: ...
2
votes
3answers
563 views

Natural merge sort in C

I have this C implementation of the natural merge sort: ...
3
votes
2answers
321 views

Slow merge sort

...
2
votes
2answers
527 views

Implementation of merge sort in Python

I was working on an assignment and I was hoping to know if the merge sort algorithm I wrote in Python was not making any unnecessary computations. ...
4
votes
4answers
438 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. ...
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\$ ...
5
votes
2answers
1k views

Counting inversions in C++ via mergesort and vectors [closed]

I have a text file that contains 100,000 numbers from 1 ~ 100,000 in an unsorted manner (no duplicates). The name of the file is "IntegerArray.txt" My task is to count the number of inversions in ...
8
votes
1answer
361 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 ...
3
votes
1answer
539 views

Natural merge sort in Java - follow-up 3

(See the previous iteration.) Now I have optimized my natural merge sort: Suppose the input sequence is $$\langle 2, 1, 4, 3, 6, 5, \dots, n, n - 1 \rangle.$$ My previous iterations would degrade ...
5
votes
4answers
1k views

Merge two sorted linked lists without recursion

Is this an effective way for merging two lists? It seemed too long. struct Node { int item; Node *next; }; Method: ...
1
vote
1answer
155 views

Merge sort in Clojure

I made my own version of merge sort: ...
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 ...
1
vote
1answer
155 views

Mergesort in C++

I'm flexing the C++ muscle and came up with the following implementation of Mergesort. Any suggestions as to the implementation and style are welcome. ...
2
votes
2answers
131 views

Run-aware merge sort

The concept is very, very simple: let's do merging run by run (a run is a range without decrement). ...