MergeSort with minimum allocations

The most recent assignment in my data structures class was writing a sort comparison, including a MergeSort. I realize that MergeSort can't be in-place, but I wondered if there was a way to keep the memory allocations to a minimum. I came up with this, which uses one extra buffer (the same size as the source array). After each pass, the source buffer becomes the target and vice versa. Timings indicate that (for arrays containing random numbers), this beats a quicksort. (Apologies for reformatting introduced by HTML...)

int *IterativeMergeSorter::Sort() {
int* src = mArray;
int* tgt = new int[mLength];
for (int swapSize = 1; swapSize < mLength; swapSize *= 2) {
for (int j = 0; j < mLength; j += (2 * swapSize)) {
int start = j;
int sizeOfSrc1 = min(swapSize, mLength - start);
int src2Index = start + swapSize;
int remainder = max(0, mLength - src2Index);
int sizeofSrc2 = min(swapSize, remainder);
Merge(&tgt[start], &src[start], sizeOfSrc1,
&src[src2Index], sizeofSrc2);
}
int* temp = src;
src = tgt;
tgt = temp;
}
if (src != mArray) {
memcpy(mArray, src, mLength * sizeof(int));
tgt = src;
}
delete[] tgt;
return mArray;
}

Erratum (part 1) for D. S. Malik's "Data Structures Using C++"

I am currently taking a Data Structures course at Chabot College. Let's just say I'm aspiring to be a Junior Programmer (only half-kidding...). The course uses the textbook (copyright 2003) mentioned in the title of this post. I realize that no textbook is perfect, but there is at least one error that will have repercussions on the grades of the students that use this text.

In table 5-7 on page 331, the text describing the pop_front method on the STL list container says

Removes the last element from the list.

Unless I'm missing something, this should read "Removes the first element from the list." See also this.

This will have repercussions on student's grades because there is a question in the on-line materials that was directly lifted from this sentence. When I took that quiz I kept getting this question wrong, and couldn't understand why. I then went back and re-read the chapter and saw this.

Caveat Emptor.

Going Paperless: Day 5

We get three newspapers at my house: the New York Times, the San Francisco Chronicle (as long as it remains in business) and the weekly freebie San Leandro Times. I go for the NYT first and my wife goes for the Chron. I will scan the headlines of the main and "Local" sections of the Chron, and (more often than not) read the comics in the lulls during preparing dinner.

The laptop just won't work for this.

First, it sleeps too frequently (probably because it's on battery). This can be changed.

Secondly, I don't like the idea of getting food on it (as opposed to the physical paper).

Thirdly, I read articles in the paper by first scanning them, taking in the first sentence of each paragraph. If I then want more information, Ithen go back and read the article in more detail. The laptop screen isn't big enough for this.

So I'm 1 out of 3:

• Not really worth reading the news on the laptop
  
• Not worth replacing pencil and paper for jotting notes
  
• Definitely worth watching Hulu (and whatever comes after)
  

Going Paperless: Day 4

I have a habit of jotting notes to myself. These notes are usually list of items (sometimes related items, sometimes not) that are just reminders. Each item is usually only a few words, but just enough to put me on the path to the full idea.

The second part of this "paperless" test was to determine if I could use the laptop for that purpose. Most of the notes that I jot to myself end up in electronic form anyway (usually expanded with more context). Wouldn't it be good to avoid that intermediate step?

I don't think this is going to work. It's like the time you realize (when trying to write a networked application) that bandwidth is not enough, you also need low latency. Laptops (and TVs and cellphones) are getting slower to "boot up," not faster.

I don't consider this test a failure. Learning something always counts, so I don't consider the experiment a waste of time. Perhaps if I ever find a cellphone I like and can afford, that will replace pen-and-paper.

Going Paperless: Day 3

This morning I read the whole front page of the New York Times paper edition while my laptop was installing the latest Windows updates.

I also realized that the primary reason I don't like the NYT web site is that it is too hard to quickly scan the headlines, unlike the paper edition. Hello, Google News?

Thirdly, while making cheese & tortillas for breakfast (I'm a FIFO kinda guy when it comes to the refrigerator), I realized that getting cheese grease on the keyboard was probably not a good idea. (Also, I can't afford to spend thousands of dollars on a Toughbook.)

It looks like the laptop is losing as far as reading the paper is concerned, at least for the way that I like to absorb the news.

Going Paperless: Day 2

Today I read some of the paper edition of the local freebie weekly while waiting for my laptop to reboot after a failed shutdown. After the laptop came back up, I went from the main NYT page to "Today's Paper" and read some articles from there. I also tried to get to the New York Times "Reader" (which looks like it shows images of the paper edition) but couldn't find a version that I didn't have to pay for. I already pay for the paper edition. I'll give the Reader another try tomorrow.

Last night I plugged the headphones in and watched some TV on Hulu. Enjoyable, but I wonder how Hulu is going to stay in business with only public service announcements for "advertising?"