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

learn more… | top users | synonyms

1
vote
0answers
20 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: ...
-3
votes
0answers
17 views

Merge sorting 10000 random elements [closed]

0 down vote favorite I am having an issue with my merge sort, when I print out my sortedArray it only returns [ 0.0, 0.0.....] Im not sure if there is an error in my sort code or in my print line or ...
1
vote
1answer
40 views

merge sort implementation 7

Please look at the above code ...
3
votes
1answer
503 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 ...
2
votes
2answers
71 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
69 views

Merge sort Python implementation

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

Bottom up (iterative) mergesort in C

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

Mergesort algorithm in C

I have this mergesort implementation that has exactly the same API as qsort: mergesort.h: ...
5
votes
3answers
248 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
90 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
90 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
45 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
64 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
59 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
66 views

Java merge sort implementation

Is this a good implementation? ...
5
votes
1answer
80 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 ...
2
votes
1answer
54 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
65 views
4
votes
1answer
118 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:...
3
votes
3answers
108 views

Natural merge sort in C

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

Slow merge sort

...
1
vote
2answers
58 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. ...
5
votes
4answers
173 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. ...
7
votes
2answers
182 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
111 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 ...
7
votes
1answer
90 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
50 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
218 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
60 views

Merge sort in Clojure

I made my own version of merge sort: ...
4
votes
3answers
100 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
121 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. ...
1
vote
2answers
87 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). ...
3
votes
0answers
126 views

Parallel Merge Sort in Scala

I have been trying to implement parallel merge sort in Scala. My current implementation is about as fast as .sorted, but I have no idea what would be the right ...
5
votes
4answers
2k 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 ...
5
votes
3answers
211 views

C++ implementation of merge sort

I am studying the merge sort algorithm and implemented it. In the mergeSort function, I am allocating two new vectors. Can I do it without allocating extra memory? ...
3
votes
1answer
124 views

Merge Sort - Using Ruby and Recursion

I am implementing the algorithms of Course: Coursera Algorithm I. I implemented the Merge-Sort using recursion and although it sorts correctly I am not sure if it is a correct implementation of this ...
1
vote
0answers
57 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 ...
1
vote
2answers
369 views

Bottom up mergesort in C++

See the next iteration. I have this C++ implementation of bottom-up mergesort (mergesort using iteration instead of recursion): bottom_up_mergesort.h: ...
5
votes
5answers
253 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 ...
7
votes
2answers
197 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 ...
3
votes
1answer
60 views

Another Scheme Mergesort

Here's a merge sort I wrote trying to learn Scheme. ...
4
votes
1answer
538 views

Sorting a linked list using mergesort

This sorts a linked list using mergegort. Can you please critique my code and provide your thoughts on where I should improve my code? ...
3
votes
1answer
90 views

Bottom up mergesort - singly linked list

I have written the following program in Go to mergesort a singly linked list. It does bottom up merge sort and hence does not have to find the mid of the linked list. Please review the algorithm and ...
2
votes
2answers
66 views

Mergesort through recursion

Could someone kindly have a look at the recursive merge sort below and let me know if there are any improvements? I'm mainly interested in either improving the code speed or making the code shorter. <...
4
votes
1answer
242 views

Counting number of inversions

This is a HackerEarth Challenge Problem. Question: Puchi hates to carry luggage, but unfortunately he got a job to carry the luggage of his N friends in office. Each day, one of his N ...
2
votes
1answer
209 views

Bottom up mergesort in Java

See the next iteration. I have this iterative mergesort (a.k.a. bottom-up mergesort). BottomUpMergesort.java: ...
4
votes
2answers
959 views

The stocks problem - find the biggest profit that can be made

The Stocks Problem: Given an array of n integers representing the price of a stock over the course of n days, determine the maximum profit you can make if you can buy and sell exactly 1 stock over ...
2
votes
2answers
151 views

Beginner implementation of Merge Sort

This is my first time implementing a merge sort (just getting started with algorithms & data structures). Are there any obvious things I have done wrong? I am also worried that I have overused ...