Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [mergesort]

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

0
votes
0answers
19 views
6
votes
2answers
212 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 ...
1
vote
0answers
35 views

Sorts (merge, quick, bubble) in Python

I'm new to python, and I wrote the following code. Please review, critique and enhance. This project compares quicksort, mergesort and bubblesort write/test the partition routine for ...
3
votes
1answer
25 views

Python merge sort for a list containing distinct values

This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But ...
2
votes
1answer
155 views

External polyphase merge sort

For comparison with other external sorting algorithms, I have implemented external polyphase merge sort, purported to be useful to sort large files that do not fit into main memory. More theoretical ...
2
votes
0answers
28 views

Merge sort to sort apple sizes indirectly

I am a beginner in Python and wrote this program to solve the following question. where are the areas that I can improve the code? I want to write in Pythonic Way. Any advice on how to improve my code?...
3
votes
1answer
104 views

Adaptive Merge Sort in C++

As the title says, I'm trying to implement a merge sort algorithm in C++ that's also adaptive. This is a personal exercise, and I don't have any specific application in mind. My main goal is to ...
3
votes
0answers
122 views

Linked-list natural merge sort in Python

I implemented the linked-list natural merge sort in Python, and I refered to this awesome if not poetic gist and this implementation in Go. Here is my code: ...
2
votes
0answers
112 views

MergeSort linked list implementation

I wrote a MergeSort implementation of doubly linked list, based on the MergeSort implementation of array on the textbook Algorithms 4th, which is definitely \$O(n \log n)\$. I think my linked list ...
4
votes
1answer
115 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 ...
2
votes
1answer
73 views

Merge sort implementation with various improvements

So I was working on merge sort today, and was trying to speed it up. I would like your opinion on the implementation and if it's possible to make it faster. Besides that I was wondering if there are ...
3
votes
0answers
30 views

Implementation of merge sort that takes sublinear extra space

I implemented an algorithm that takes only sublinear extra space as required in the exercise description: Develop a merge implementation that reduces the extra space requirement to max(M, N/M). (...
2
votes
2answers
83 views

Python merge sort

In Algorithms Fourth Edition by Robert Sedgewick and Kevin Wayne, the exercise 2.2.10 states that: Implement a version of merge() that copies the second half of a[] to aux[] in decreasing order ...
0
votes
1answer
85 views

Merge sort approach in Python

I'm working my way through a book on algorithms. One of the first challenges is the merge sort. I've seen this implemented before, but as the book suggested I coded one from just the method without ...
1
vote
2answers
110 views

Merge Sort code in C

Below is the code of Merge Sort for sorting an integer array in ascending order of values written by me. By looking at the code, I am thinking I can make the code more compact and secure, but not ...
5
votes
3answers
1k views

C++ code to sort a list of elements

This is a code uses mergesort algorithm to sort a list of elements.What are the possible improvements on the code?Also are there any unhealthy coding practice involved in this code? ...
3
votes
1answer
273 views

Merge sort Java implementation for an interview

I just learned Merge sort, and I really like this Merge sort implementation since it is very logical and very easy to follow. If I was asked in an interview to implement merge sort, will this ...
5
votes
2answers
122 views

Move friendly merge sort - follow-up

This is a follow up to this question. I'm only interested to see if this is implemented correctly for move-only types. ...
7
votes
3answers
1k views
3
votes
2answers
239 views

Merge two sorted lists in Python

Merge two sorted lists ...
2
votes
2answers
209 views

Bottom up merge sort in Haskell

Although this sort works on Int lists < length million, when the stack overflows, the last clause of the merge function definition looks odd to me, recursing in 2 places. Is there clearer way to ...
2
votes
0answers
49 views

Mergesort in Python optimization

I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster ...
5
votes
2answers
143 views

Writing Merge Sort in C++

I am learning programming online and currently watching CS50 lectures, in third lecture, professor introduces us to merge_sort though only through pseudo code, so I wanted someone to review my ...
1
vote
3answers
231 views

Using mergesort to sort lexicographically

The program should (and does) the following (paraphrased assignment): There is a catalogue with a list of motorcycles. They have a - Name (spaceless string of 20 chars) - Price (int < 99 ...
3
votes
2answers
226 views

Mergesort linked list in C++

My teacher gave us an exercise. We have to sort as quickly as possible. The fastest one gets a reward. On my own system, I am sorting 125000 words within 1.2 seconds. On my teacher's system that is 0....
1
vote
1answer
364 views

Recursive merge-sort inversion count algorithm very slow

I am trying to implement a recursive count of inversions in a list of integers by using merge sort and counting the number of split inversions on each recursion. My code works but runs painfully ...
2
votes
1answer
105 views

merge_sort and unit testing

I made a merge sort and wanted to ask for code review. It passed all of the unit testing. The idea behind the classic Mergesort algorithm is to divide an array in half, sort each half, and merge the ...
5
votes
1answer
289 views

Multi-threaded in-place Mergesort on Java

What is an efficient way to implement the Mergesort algorithm in Java such that it meets the following criteria: Must be multi-threaded. Must retain the Mergesort time complexities. Must be in-place ...
1
vote
1answer
77 views

Merge Sort Cleanup

I am re-learning my fundamental algorithms, and have been told my Python is overly verbose. Can you take a look at my merge sort algorithm and let me know how you would clean it up and make it more ...
1
vote
2answers
58 views

Mergesort, instrumented for counting reads and writes

I have just finished an implementation of mergesort, and I was wondering if I can further reduce the amount of reads and writes. I have looked at it for a while, and to my eyes, I cannot see anything ...
7
votes
2answers
960 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 <...
0
votes
1answer
354 views

Mergesort implementation, eliminating slice()

I am having trouble coming up an alternate solution to my mergesort. I think using slice is an expensive operation. I have two implementations, recursive and iterative. ...
4
votes
1answer
324 views

Merge Sort efficiency in Python

I am writing a script that takes in many sorted .dat files. I have included sample data but the dataset is quite large. The desired outcome is to have one file with an alphabetically sorted list of ...
2
votes
1answer
171 views

C++11 merge sort implementation

I've tried implementing merge sort in C++ just by looking at this Wikipedia graphic. Comparing my code to other merge sort code implementations, it doesn't look quite the same at first glance. Have I ...
2
votes
2answers
655 views

Merge sort a given list in Python

Problem: Implement merge sort in python. Don’t use Python’s built in sort or sorted. Assume your inputs will be sufficient for the memory you have. How should I make this code better? ...
2
votes
2answers
277 views

Generic Merge Sort in C++

I wanted to implement merge sort in a generic way. I was not sure whether I should use the iterator or the container for the template type. I did not find a way to infer the container type using ...
2
votes
1answer
39 views

C - non-recursive mergesort on lists

Continuing my foray into classic structures and algorithms, I've tried to implement merge sort for doubly-linked lists. From my (limited) testing it seems the thing I've concocted works, but several ...
4
votes
2answers
438 views

Bottom-up singly linked list merge sort in C++

This is an implementation of a singly linked list merge sort I did on paper during a job interview recently, using a bottom-up approach. The requirement was simply "implement a merge sort for a ...
4
votes
1answer
124 views

Recursive Ruby merge sort

I have implemented a merge sort in Ruby. (Yes, I know, there's Array#sort) I would like to get feedback on code quality and optimization. ...
2
votes
1answer
336 views

MergeSort implementation in Python

I wanted to share a bit about how to implement your merge sort. Merge sort is a divide and conquer algorithm that breaks down an array into smaller pieces and eventually pieces them back together one ...
1
vote
1answer
260 views

Merge sort implementation in C++

I was wondering if this implementation of merge sort could be improved. Are there any things that I have done wrong? ...
0
votes
1answer
587 views

Merge two sorted lists

There are many if-else conditions in my code Question 1: I am looking for suggestions to minimize if else conditions. Also, Code in Step 1 and Step2 is almost ...
-3
votes
1answer
65 views

MergeSort - Is this actually MergeSort?

Will this code actually work as MergeSort? This is working to sort the array but is it MergeSort? My faculty did approve of this but he probably did not see the code properly and I need some serious ...
6
votes
4answers
912 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 ...
2
votes
1answer
115 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 ...
3
votes
1answer
265 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 ...
4
votes
1answer
1k views

Merge two integer lists in Pascal

The purpose of the code is to merge two ordered lists (list 1 : 5 integers, list 2 : 8 integers) into another third ordered list, whilst maintaining their order, while entries that appear in more than ...
3
votes
3answers
181 views

Interleave two sorted arrays

To learn Rust, I tried to write a function that takes two sorted arrays of integers and interleaves them into one longer sorted array. Is this approach ok? Have I made any mistakes? ...
2
votes
1answer
145 views

Program to implement Merge Sort Algorithm

So, I just learned the Merge Sort algorithm from Youtube and tried implementing it. Is this the most efficient way to do it? ...
2
votes
1answer
702 views

Merge K Sorted List

Merge k sorted linked lists and return it as one sorted list. The definition of the ListNode class and the signature of the ...