Stack overflow with merge sort algorithm

Question

I'm trying to order a file with 577000 lines by year. I'm putting the information of which line in a doubly linked list. To order the file I tried to implement the merge sort algorithm , but because the algorithm is recursive when ordering a large quantity of information the algorithm doesn´t work because of the overflow of the stack memory. Can someone help try to find a more efficient algorithm that doesn´t crash and doesn´t take too long ?

From a comment:

The dates ranger from 1730 to 2013

Use loops instead of recursion? Recursion is just a fancy kind of loop anyway, but one that is prone to faults like stack overflow. — Some programmer dude
– Some programmer dude, Commented May 20, 2018 at 18:45
A correctly written merge sort cannot cause stack overflow with a data size as small as N = 577000! it would recurse only max ~**20 times**. — Antti Haapala
– Antti Haapala, Commented May 20, 2018 at 18:55
I recommend using the QuickSort sorting algorithm (for C language, you'll find a lot of ready-made example codes on the Internet). Forget about what system or platform you are using. Linux ? Windows ? MS-DOS :) ? And what version of the system ? Which C-language do you mean: C / C++ / C# ? You write about 577k rows, but what type are the data ? Do you want to sort string data or numeric data (integer, float, ...) ? Why did not you create your source code at the same time ? — s3n0
– s3n0, Commented May 20, 2018 at 19:05
I'm using c language just c. Using linux ubuntu 16-04. I'm saving in which node a structure of data. The problem of sorting at the same time that I'm saving is that is takes too long to store the data and order it. — Carlota Medeiros
– Carlota Medeiros, Commented May 20, 2018 at 19:19
So each line contains a year. Like: "1978 some text", right? And you need to sort it by year only? What are the range of years? 1900 to 2100 or ... ? To give a good answer we'll need such information. With the information I have, it seems that you should organize data as you read it. — 4386427
– 4386427, Commented May 20, 2018 at 19:48

4386427 · Accepted Answer · 2018-05-20 20:22:19Z

1

You don't need a complex sorting. Given that you only need to cover about 300 different years this is what I would do.

Make an array[300] of linked list. Index zero is the linked list for the year 1730. Index 1 is the linked list for year 1731.

Now when you read a new entry from the file, you can find the array index by subtracting 1730 from the year read. Then you add the element to the linked list at that index.

When the whole file has been read, you put all the linked list together to a single linked list starting from index 0.

Now you have a linked list sorted by year.

edited May 20, 2018 at 20:22

answered May 20, 2018 at 20:09

4386427

44.7k4 gold badges44 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Stack overflow with merge sort algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related