Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
39 views

Recursive Merge Sort Algorithm (Python)

Merge Sort Merge Sort algorithm is a general-purpose comparison-based sorting algorithm. Most implementations produce a stable sort, in which the order of equal elements is preserved. Just for ...
3
votes
1answer
38 views

Iterative Merge Sort Algorithm (Python)

Merge Sort Merge Sort algorithm is a general-purpose comparison-based sorting algorithm. Most implementations produce a stable sort, in which the order of equal elements is preserved. Here, our ...
1
vote
2answers
110 views

Merge k sorted lists in Java

I hava a question similiar with mege in Python but I am trying to write Java code. Here is my code: The input is: The first line - a number of arrays (k); Each next line - the first number is the ...
4
votes
1answer
84 views

LeetCode: Merge k sorted lists C#

https://leetcode.com/problems/merge-k-sorted-lists/ Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. ...
1
vote
0answers
47 views

Vector of numbers where merge sort is slow

I'm starting to study sorting algorithms in Python. Merge Sort has a complexity at best and worst cases \$\mathcal{O}(n\log{}n)\$, I want generation a list where Merge Sort is slow but I would some ...
5
votes
4answers
193 views

C-based hash matching cracker

How can I improve this hash matching program using either abstraction or search/sort algorithms? We briefly were introduced to searching methods such as bubble sort and merge sort, but I'm not sure ...
4
votes
4answers
87 views

MergeSort in Javascript

I implemented the following mergesort algorithm in JavaScript, but I want to know your opinion about if is possible to do better than this. ...
1
vote
1answer
48 views

What are the downsides of my Mergesort implementation?

Could I ask you to evaluate my implementation of mergesort? I think that it's consistent with \$\mathcal{O}(n \log n)\$ complexity but has a downside that I create a new ...
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 ...
6
votes
2answers
677 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 ...
4
votes
2answers
74 views

Merge sorted lists

I want to write a function that merges two sorted lists in Python 3. For example: >> merge_lists([2, 5, 9], [1, 6, 8, 10]) [1, 2, 5, 6, 8, 9, 10] My ...
8
votes
0answers
46 views

Parallel merge sort with thread- and bufferpooling

I did wrote this parallel merge sort with no external dependencies. I tried to make use of modern C++ as much as possible. Can you please tell me how it is? ...
3
votes
2answers
134 views

Merge Sort C++11 C++17

Question Any way I can optimize this further using new C++11 or C++17 features? Would also like feedback on my variable naming, memory management, and style (notice my placement of ...
2
votes
1answer
279 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 ...
1
vote
0answers
48 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
26 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 ...
3
votes
1answer
124 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
245 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: ...
8
votes
1answer
372 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 ...
2
votes
0answers
187 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
258 views

Sorting a singly linked list with natural merge sort in C

This C program implements a so-called natural merge sort that identifies existing runs in the list and exploits them in order to sort in sub-linearithmic time whenever possible. The running time of ...
4
votes
1answer
219 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
76 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
35 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
86 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
100 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 ...
7
votes
1answer
253 views

Functional K-way merge (Merge k sorted sequences)

I've implemented a functional k way-merge algorithm to merge k sorted sequences of any type T. I used scalaz's Heap since the Scala standard library does not provide an immutable heap. Any suggestions ...
5
votes
1answer
402 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
2answers
131 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 ...
2
votes
2answers
241 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 ...
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
351 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
131 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. ...
3
votes
2answers
290 views

Merge two sorted lists in Python

Merge two sorted lists ...
2
votes
0answers
56 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
157 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
410 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
322 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....
5
votes
2answers
7k views

Merging Two Sorted Lists in Python In Linear Time

I am trying to implement a merge of two sorted lists of integers in Python using only the basic list abstract data type operations. That is, I do not want to use ...
1
vote
1answer
443 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
150 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 ...
8
votes
4answers
3k views

Given two sorted arrays, add the elements of the second array into the first

In Cracking the Coding Interview by Gayle Laakmann McDowell, there's a question that asks you to write code for the following: Given two sorted arrays, A and B. Write a method merging the elements ...
1
vote
1answer
86 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 ...
6
votes
1answer
14k views

Recursive merge sort in python

I'm very new to python, however not new to programming as I've been doing C for some time. So here is my practice of a merge sort, I looked at other questions however they were many more lines ...
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. ...
4
votes
2answers
500 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 ...
1
vote
2answers
71 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
1k 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 <...