Write a program that merges two ordered list objects of integers into a single ordered list object of integers. Function merge should receive references to each of the list objects to be merged and reference to a list object into which the merged elements will be placed.

Question

What will be an ideal response?

Answer 1

```
#include
using namespace std;

#include "List.h"

template< typename T >
void merge( List< T > &first, List< T > &second, List< T > &result )
{
List< T > tempFirst( first ); // create a copy of first
List< T > tempSecond( second ); // create a copy of second
T value1;
T value2;

tempFirst.removeFromFront( value1 );
tempSecond.removeFromFront( value2 );

while ( !tempFirst.isEmpty() && !tempSecond.isEmpty() )
{
if ( value1 <= value2 )
{
result.insertAtBack( value1 );
tempFirst.removeFromFront( value1 );
} // end if
else
{
result.insertAtBack( value2 );
tempSecond.removeFromFront( value2 );
} // end else
} // end while

// Insert the values currently in value1 and value2
if ( value1 < value2 )
{
result.insertAtBack( value1 );
result.insertAtBack( value2 );
} // end if
else
{
result.insertAtBack( value2 );
result.insertAtBack( value1 );
} // end else

// Complete the insertion of the list that is not empty.
// NOTE: Only one of the following 2 while statements will execute
// because one of the lists must be empty to exit the preceding while
if ( !tempFirst.isEmpty() ) // items left in tempFirst
{
do
{
tempFirst.removeFromFront( value1 );
result.insertAtBack( value2 );
} while ( !tempFirst.isEmpty() );
} // end if
else // items left in tempSecond
{
do
{
tempSecond.removeFromFront( value2 );
result.insertAtBack( value2 );
} while ( !tempSecond.isEmpty() );
} // end else
} // end function merge

int main()
{
List< int > list1;
List< int > list2;
List< int > result;
int i;

for ( i = 1; i <= 9; i += 2 )
list1.insertAtBack( i );

list1.print();

for ( i = 2; i <= 10; i += 2 )
list2.insertAtBack( i );

list2.print();

merge( list1, list2, result );

cout << "The merged list is:\n";
result.print();
return 0; // indicates successful termination
} // end main
```
The list is: 1 3 5 7 9
The list is: 2 4 6 8 10
All nodes destroyed
All nodes destroyed
The merged list is:
The list is: 1 2 3 4 5 6 7 8 9 10
Destroying nodes ...
1 2 3 4 5 6 7 8 9 10
All nodes destroyed
Destroying nodes ...
2 4 6 8 10
All nodes destroyed
Destroying nodes ...
1 3 5 7 9
All nodes destroyed