merge sort

[Tsweeney]

Help! I need some help on how to write a func. that takes a list as an arguement and returns two equal lists. Any hints? I am pretty new to this, and am pretty lost!

[GFreak45]

what do you mean by a list? an object? an array? return 2 lists? you cant have 2 returns... you could pass an address (a variable argument) and use that as a "return" and then have a normal return

[Tsweeney]

I am working on a merge sort function that will split a vector approx. halfway.

[TheDestroyer]

You don't need to split the vector to do merge sort. I have implemented merge sort before. Do it smart, not hard; I mean, why would you waste efforts with copying? you can just run 2 variables along the first half and second half (and then over the first half half and the second half half, etc...), and through those variables do the checks you want to do for greater or less. Right?

[GFreak45]

I dont think he means making 2 vectors of the same size, i think he is referring to when you split up the list while merge sorting, you run the sorting algorithm on the main list and it breaks it up into 2 lists of ~equal length, and it keeps doing this until it gets down to a size of 2 and sorts those then merges...

ie:

5 8 2 4 3 1 9 7

->

5 8 2 4 | 3 1 9 7

->

5 8 | 2 4 || 3 1 | 9 7

sort:

5 8 | 2 4 || 1 3 | 7 9

merge:

2 4 5 8 | 1 3 7 9

merge:

1 2 3 4 5 7 8 9

it results in a complexity of O(n*log(n)) which is much faster than the bubble sort complexity of O(n^2)

[Tsweeney]

#include "stdafx.h"
#include<iostream>
#include<list>
#include<cstdlib>
using namespace std;
list<int> L, L1, L2; //lists of ints
L.assign {50,(1+rand()%6)}; //fill list

I have to use a linked list for this project, so here is my attempt at initializing it
with 50 random ints. will this work?