Questions tagged [mergesort]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
484 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
47 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
537 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
165 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
376 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
408 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
709 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
67 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
1k 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
118 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
325 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
307 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
836 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
263 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
431 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
454 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
722 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
278 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
550 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
362 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
723 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
3k 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
14k 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
158 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
78 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
108 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
1k 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
15k 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
618 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
427 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
282 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
121 views

Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
3
votes
2answers
78 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
870 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
249 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
440 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
271 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
269 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
68 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
172 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
123 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
15k 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
485 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, ...