Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
6
votes
4answers
957 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
117 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
305 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
222 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
146 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
801 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 ...
7
votes
1answer
249 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 ...
0
votes
1answer
359 views

C++: Merge Sort Implementation

I have this code for Merge Sort. I want to improve this code. I have learned Here that we should use Iterartor so that we can use any container. How to use iterator in this code. ...
1
vote
1answer
373 views

Merge Sort implementation with generators and recursion

Just beating the dead merge-sort horse, this time with generators and recursion! What do you think? p.s. Not entirely sure why stack overflow needs me to post more details on a code review. I'm ...
8
votes
1answer
1k views

Generic Template implementation of merge sort in C++

A few month ago I wrote several basic sort algorithm for educational purposes as generic as possible in C++. In a few days time I want to present some of that stuff in my class but before that I ...
3
votes
2answers
660 views

Merge Sort in Kotlin

I started learning kotlin recently,with some background in java. So I wrote a merge sort algorithm in kotlin. I am looking for best practices in kotlin and looking for this code review. I also ...
3
votes
1answer
264 views

Selection algorithm using merge sort and IEnumerable

For educational purposes, I wrote a selection algorithm based on a Merge sort. I would like to improve performance. ...
2
votes
1answer
535 views

Python Merge Sort Implementation

I doing some algorithm reviews and am soliciting opinions on my implementation of the Merge Sort in Python. Anything from readability to optimization is fair game. In particular, I am wondering if ...
4
votes
3answers
350 views

C++ Merge Sort Implementation - Pt2

Following the review of my old merge sort implementation here, it appears that the biggest improvement to make was to use iterators instead of copying the vectors. ...
2
votes
1answer
562 views

Java mergesort with generics

The following is my implementation of mergesort with Java generics. I chose to use the iteration variables a_iter and b_iter to ...
9
votes
4answers
2k views

C++ Merge Sort Implementation

Edit: A follow up question can be found here. My first try at mergesort, without resorting to any references: ...
7
votes
3answers
12k views

Merge sort implementation with vectors

I'm new to algorithms. To be honest I am not really sure if my implementation is right. However, the output is sorted correctly in ascending order so perhaps it's correct. Please feel free to give ...
-1
votes
1answer
155 views

Merge sort for an integer array in Ruby

I've implemented merge sort an integer array. Should I change them to more meaningful names? Overall, any further suggestions on this code? I would like to improve my coding style and to shorten the ...
3
votes
0answers
76 views

Functional Merge Sort in Python with only boolean variables to control fall off logic

Merge Sort I have just implemented this merge_sort, and this is also my first algorithm implemented in Python, I am totally open to feedback about how to better use python. I am using Arrays instead ...
6
votes
1answer
100 views

Merge sort practice

Never written a merge sort for huge files before. So after this mornings question I though I would give it a go. ...
5
votes
2answers
994 views

Non-recursive implementation of MergeSort

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...
31
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. ...
3
votes
4answers
530 views

Merge two sorted arrays in NASM

I have the following function which I wrote in NASM to merge two sorted arrays. Its not a standalone, but its supposed to be compiled into a .o file and then linked ...
0
votes
1answer
401 views

Java merge sort implementation efficiency

The problem was to implement merge sort algorithm in Java, where I recursively split and merge the array until I have the sorted array. Even though the code is working properly, I feel it is verbose ...
4
votes
1answer
255 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 ...
1
vote
1answer
119 views

Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
3
votes
2answers
76 views

Mergesort that has `man 3 qsort` ANSI C prototype

I have taken a look at these review questions: one, two, three and four and would still like to ask you to review my implementation of mergesort that follows the ...
0
votes
3answers
44 views

Could this be considered a valid mergesort? [closed]

I tried to do a mergesort function for an assignment without importing merge from heapq: ...
4
votes
1answer
754 views

Mergesort vs Quicksort Timing in Python

I have implemented Mergesort and Quicksort in Python and have noticed that Quicksort runs two times as fast as Mergesort. Is this a property of the algorithm or is Mergesort coded inefficiently? Are ...
1
vote
1answer
232 views

Merge sort in declarative style with JavaScript

ES6 syntax helps to write code in a declarative style, which is exactly what I am trying to achieve here. Any advice to make my code "more declarative" (and easier to read) is welcomed. ...
1
vote
2answers
422 views

Merge sort implementation using divide-and-conquer

I was told in an interview to write a program for implementing merge sort on the concept of divide-and-conquer. ...
1
vote
3answers
136 views

Merge Sort Java

This is the merge part of my solution. Method merge merges two already sorted lists. I feel the code I wrote isn't the best implementation. Please review the code ...
4
votes
1answer
264 views

Counting inversions with merge sort

I am piggybacking an iterator-based implementation of merge-sort to count array inversions. My first correct solution looks as follows: ...
3
votes
1answer
211 views

Implement the merge sort + binary search algorithms to filter and merge sort two arrays

I wanted to take my own shot at a merge sort array implementation. I took on the prompt from Rahul's post. The goal (altered a little for my purposes): Implement a solution capable of merging &...
2
votes
1answer
67 views

If given two sorted arrays where first containing -1, merge into one sorted array

If given two arrays arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1] arrayTwo = [1,10,17,56] Both the array's are sorted but array1 consists -1 in between the ...
3
votes
1answer
166 views

Java Merge Sort

I implemented a merge sort in Java. Is there any way to improve it? I suspect that in particular the merging part could be improved. Note: I deliberately removed all the comments. ...
2
votes
1answer
142 views

Sorting algorithms and command-line interface

I have implemented both some sorting algorithms (namely bubble sort and merge sort), as well as a command-line interface, in ...
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
122 views

Merge sort implementation weirdly faster than system sort

I wrote the following functions to merge sort an array of Comparables. It seems to work well (I am testing the output to make sure it is sorted). It takes about 2.5 ...
6
votes
1answer
13k 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 ...
3
votes
1answer
431 views

Merge sort C++14 implementation

Here is my merge sort c++ implementation. Looking for code improvement and optimization opinion. Just one question which is better *k++ = *i++; or, ...
2
votes
1answer
2k views

Recursive merge sort in C++

Any suggestions on how to improve this code (other than arbitrary call-stack depth)? ...
6
votes
2answers
1k views

Implementation of merge sort algorithm in C++

This is my implementation of "merge sort" in C++. I'm still a newbie at C++ so: Have I understood how merge sort works and implemented it in the right way? Have I used any bad practices? How could ...
3
votes
0answers
305 views

Merge two sorted linked lists in C++

Should I be using std::move or copy when passing LNode in the LinkedList constructor instead ...
-1
votes
1answer
141 views

Mergesort - Database

Code directory structure: ...
1
vote
1answer
327 views

Merge sort and linked list implementation

I implemented merge sort with my own linked list for a school project. I was not allowed to use anything but the methods you see in the list. It seems to work properly, however, when running the ...
5
votes
2answers
117 views

Classic merge sort

Here is my code for classic merge sort. My question is, each time I create a new list result to merge sub-parts, is there a way to save the space -- not creating a ...
3
votes
1answer
72 views

Implementation of mergesort in Java

I'd like to know if the following code is a good implementation of MergeSort? I tried some examples and the code was right, so I guess that the algorithm works correctly. ...
6
votes
5answers
2k views

Merge two sorted lists of numbers

Inputs are two sorted lists (of the same length) of numbers. I would like to return a new merged, sorted new list. I have written the following code, but most lines are used to deal with the end case. ...