Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
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
132 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
449 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 ...
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 ...
5
votes
3answers
534 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
448 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
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 ...
1
vote
2answers
883 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: ...
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 ...
7
votes
2answers
848 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
401 views

Another Scheme Mergesort

Here's a merge sort I wrote trying to learn Scheme. ...
4
votes
1answer
2k 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
290 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
79 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. <...
5
votes
3answers
705 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 friends,...
2
votes
1answer
602 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
3k 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
228 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 ...
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 ...
5
votes
1answer
816 views

Merge sort implementation in JS

Just for learning and practicing I've created a completely recursive version of the merge sort algorithm. I've tested it a little bit and it seems working, but I'm quite sure that it can be largely ...
5
votes
2answers
635 views

Merge Sort algorithm

I just read and experimented with C++ implementation of the merge sort algorithm from the Wikipedia page. During the experiments I have slightly modified the source code and would like to know how ...
5
votes
2answers
436 views

Merging sorted arrays

I'd like to know if it's ok to write like this or there is a better, prettier way to do this. The merging itself is ok. I'm more interested in dealing with the situation when one of the arrays is ...
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. ...
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 ...
2
votes
1answer
704 views

Fast merge sort in JavaScript

When developing a user interface that allows sorting by various different fields, I noticed that Array.prototype.sort() is extremely slow for large inputs. After ...
1
vote
1answer
197 views

Parallel natural merge sort

Continuing working on Natural merge sort, I have parallelized it. Requires \$\Theta(N)\$ space and runs in $$\Omega(N + \frac{N}{P}) \cap \mathcal{O}(N + \frac{N}{P}\log_2\frac{N}{P})$$ time, where \$...
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: ...
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 ...
2
votes
1answer
288 views

Mergesort using map-reduce, multithreads, buffers and condition variables

I wrote a map reduce program which uses multi threads, bounded buffers, condition variables. It works perfectly for some types of inputs. In the program there are N mappers, R reducers, 1 merger. ...
1
vote
3answers
71 views

Merge sort implementation: sorting feels clunky

I got bored and decided to make a merge sort from scratch. I like everything, except for my "merging" of the two arrays into a sorted array inside the for loop. I ...
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 ...
5
votes
1answer
613 views

Mergesort a LinkedList

I have made an attempt to write the mergesort routine on a LinkedList in Java. It will be great if somebody can review my implementation and point out the issues ...
3
votes
1answer
286 views

Sort a linked list with merge sort in C

This is my version of a linked list in C. The function mergeSort requires a reference to the first and to the last nodes, as well as the indices of the first and ...
5
votes
1answer
2k views

Mergesort bottom-up

I am looking for suggestions on how to improve my mergesort. My teacher explained the recursive mergesort and left the bottomUp one as an assignment. I have ...
4
votes
3answers
927 views

Merge sort implementation and improvements

I would like your opinion on my Java implementation of the merge sort algorithm on an integer array, since I'm not really into algorithms I'd like to know from you if this is a correct implementation ...
2
votes
3answers
385 views

Is this an efficient way to implement Merge Sort in C++?

I am studying C++ and I wrote the following Merge Sort algorithm. I need some comments from skilled C++ programmers to understand where it can be improved, in terms of execution time, memory usage and ...
7
votes
2answers
4k views

Merge sort in C++ with iterators

I implemented merge sort with C++ and would like to get some feedback. ...
3
votes
2answers
183 views

Merge Sort Implementation: Space Usage

I have made a merge sort algorithm but am unsure of the 'Space Usage' of the algorithm. ...
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? ...
-1
votes
1answer
1k views

Merge sort optimization and improvement

How to optimize this merge sort code to make it run faster? And how to call merge_sort function without user input by declaring necessary array in the code? ...
3
votes
1answer
279 views

Is this an optimal implementation of merge sort?

I am taking an algorithm course and we are to implement merge sort that handles list of elements with even or odd number of elements and handles duplication, so I wrote this function: ...
4
votes
2answers
955 views

Sorting function that also works with containers having only forward iterators

I was playing around with some code trying to implement a sorting algorithm in C++ that also works with singly linked lists. Since the merge routine of mergesort only scans forward, implementing a ...
5
votes
3answers
3k views

Merge sort with raw C++ array

Merge function: ...
4
votes
2answers
2k views

Mergesort with std::vector

I made a mergesort implementation based on this code. Please review my C++ version. ...
3
votes
1answer
2k views

3-way merge sort in Java

All those numerous merge sorts split the range in two halves. This is a modification that splits each range into 3 subranges. My demo suggests that 3-way merge sort is pretty efficient on large arrays....
4
votes
3answers
367 views

How can I optimize this mergesort?

In main: ...
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 ...
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 ...
9
votes
2answers
2k views

Merge sort using sentinels

This is my implementation of recursive merge sort, using sentinels: ...
4
votes
1answer
93 views

Mergesort and validation

I have written an implementation of a Mergesort in Python3. An Ideone with the implementation is available. Any suggestions for improvement or any criticisms? ...