Mergesort can be done in-place for list;unlike an array.
However,I have not found a reference yet which explains how this is achieved.
Any pointer is appreciated.
Asked
Active
Viewed 82 times
0
IUnknown
- 9,301
- 15
- 50
- 76
-
This question has a couple of good answers: http://stackoverflow.com/q/2571049/ – blgt Jun 19 '14 at 16:55
-
Did you mean a *linked list* ? (an array is also a list) – wildplasser Jun 19 '14 at 21:36
-
possible duplicate of [Merge Sort a Linked List](http://stackoverflow.com/questions/7685/merge-sort-a-linked-list) – Jim Mischel Jun 20 '14 at 02:38
-
Did you do *any* research? Typing "merge sort linked list" into Google provided many good examples. – Jim Mischel Jun 20 '14 at 02:39
1 Answers
0
It actually is possible, though not straightforward, to implement an in-place merge sort for arrays. With linked lists the problem becomes quite simple. Each node in a linked list just has a value and a pointer to the next node. It is quite simple to break a linked list in half. Just traverse to the middle node, take its successor as the head of your second list and then set successor to null.
The merge step works just like you would expect. Don't make any new nodes, just relink the nodes from your two lists.
Wcrousse
- 203
- 2
- 10