CODEWITHSUNDEEP
cdatabasemergesortexternal-sorting
nikos
nikos

Reputation: 3013

How to sort the runs in external sorting using merge sort

I am trying to implement (in C) an external sorting algorithm of a database using merge sort for a college assignment. The available memory is buffSize blocks. I found this link very helpful:

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

but my problem is about this line of the pseudo-code, in phase one of the algorithm:

sort array a using an in-memory algorithm like quicksort

If I don't have the right to use any memory other than my buffSize space, so I cannot allocate the a array of the link, how can I sort the records that are contained into those blocks (and then store them in a temporary run file), using an in-memory sorting procedure (e.g. quicksort). My records in that case would not be in a contiguous array but rather in non-contiguous memory located blocks and I can't directly apply qsort. Any hints?

Upvotes: 0

Views: 3499

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 754600

The general approach for an external sort is:

  1. Read as much data as will fit into an array memory.
  2. Sort it.
  3. Write it out to a temporary file (keeping track of name and size and largest record, etc).
  4. Go back to step 1 until you reach the end of the data.
  5. Set up a merge tree for the files written so that you do the minimum of merges.
  6. Read a line from each of the first (only?) merge phase input files.
  7. Write the smallest (for an ascending sort) to the next temporary file (or the final file).
  8. Get a new record to replace the one just written.
  9. Go back to step 7 until there is no more data to read.
  10. Go back to step 6 to continue the merge until you're done.

You've not detailed what buffSize blocks of memory means, but there's an array a that can be sorted in memory. So, you read the data into the array. You sort the array using quicksort. Then you write the array out to disk. Repeat reading, sorting, writing until there's no more input data. Then do the merging...

Upvotes: 2

Related Questions