Solved-Lab 3- Solution

Description

1. Measuring the maximum size of dynamically allocated array

In this exercise you need to find the maximum “allocatable” size of a one dimensional array of type integer on your system. You can iteratively allocate (and free) a dynamic array while doubling the size every time until you incur failure.

2. Merge Sort using insert operation

Implement two variations of merge sort algorithm: one with the (classical) merge operation and the second where merge is replaced by a procedure named mergeByInsert. mergeByInsert(L1, L2) inserts each element of one list , say L2, into the other i.e. L1, one at a time in sorted order. Not that this Insert operation should be in place, i.e. it should use no more than one additional memory location.

Measure the time taken and space usage for each variation by the techniques implemented in the labs last week.

Here is your sample test case. The first line of the input file denotes the number of elements in the file.

Your program must simply print the sorted array at the end of execution as shown in the sample output.

Test case 1:

1 | P a g e

3. Sorting very large files

Given a very large file of few GBs of data (few billions of records stored in it). You need to sort this file. We came to know from the above exercise, the maximum size you can allocate to an array. So obviously you can’t make an array of size of a few billions. However, you can merge two sorted files of smaller size and make a larger sorted file using FILE I/O.

Use this technique to design a sorting algorithm to sort very large files: Use merge sort at the top level to create multiple files of smaller sizes. Sort these smaller files using insertion sort and then merge all of them (two at a time) in a hierarchical manner to get the bigger sorted file. You can assume that the number of records in the file is a multiple of 2.

Also, measure the time taken and space used by the techniques referred to in the last lab session.

2 | P a g e