Tech Blog

Abstract:

Merge Sort has several advantages on performance. This technique divides the whole data as like divided and conquer method but until two elements in a group. Then solves the divided parts and conquers them. The resulting efficiency of this method is that the division of problem is much less then the previous method, so the recursive call is also less. As a result we have less comparison and less computational time. Merge sort can be implemented in C to sort the file.

Introduction:

Merging is the process of combining two or more sorted files into a third sorted file. In most implementations it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It is also called Divide and Conquer where we divide the problem into a number of sub-problems and then we conquer the sub-problems by solving them recursively. Merge sort can be implemented in C to sort the file. Divide the file into n subfiles of size 1 and merge adjacent pairs of files. We then have approximately n/2 files of size 2. Repeat this process until there is only one file remaining of size n.

Working Mechanism:

Theoretically, a merge sort works as follows:
If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sub list recursively by re-applying merge sort.
Merge the two sublists back into one sorted list.

To sort A [p…r] Divide by splitting into two subarray A [p…q] and A [q+1…r], where q is the half way point of A[p…r].
Conquer by recursively sorting the two subarrays, A [p…q] and A [q+1…r].
Combine by merging the two sorted subarrays A [p…q] and A [q+1…r] to produce a simple sorted array A [p…r].


Example:

Original file:

Pass 1: ↓ ↓ ↓ ↓

Pass 2: ↓ ↓

Pass 3: ↓

Sorted file:

Pseudocode:

Merge (A, p, q, r)
n1 ← q – p + 1
n2 ← r – q

Create arrays, L[1…n1+1] and R[1…n2+1]

for i ← 1 to n1,
do L[i] ← A[p+i-1]
for j ← 1 to n2,
do R[j] ← A[q+j]

L[n1+1] ← ∞
R[n2+1] ← ∞
i ← 1
j ← 1

for k ← p to r
do if L[i] ≤ R[j]
then A[k] ← L[i]
i ← i+1
else
A[k] ← R[j]
j ← j+1

Note: We constructed two auxiliary arrays namely L and R.


Implementation of the algorithm in C:

/* An example of routine that accepts two sorted arrays a and b of n1 and n2 elements, respectively, and merges them into a third array c containing n3 elements. */

void mergearr(int a[], int b[], int c[], int n1, int n2, int n3)
{
int appoint, bpoint, cpoint;
int alimit, blimit, climit;

alimit = n1-1;
blimit = n2-1;
climit = n3-1;
if (n1+n2 ! = n3)
{
printf(“array bounds incompatible/n”);
exit(1);
}
apoint = 0;
bpoint = 0;
for (cpoint = 0; appoint <= alimit && bpoint <= blimit; cpoint++) if(a[appoint] < style="font-weight: bold;">Analysis:

Merge sort is more efficient than other sort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, merge sort is a stable sort as long as the merge operation is implemented properly. In sorting n items, merge sort has an average and worst-case performance of(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm .
In the worst case, merge sort does approximately (n ⌈lg n⌉ - 2⌈lg n⌉ + 1) comparisons, which is between (n lg n - n + 1) and (n lg n + n + O (lg n)). In the worst case, merge sort does about 39% fewer comparisons than quick sort does in the average case; merge sort always makes fewer comparisons than quick sort, except in extremely rare cases, when they tie, where merge sort’s worst case is found simultaneously with quick sort’s best case.

Types of analysis:

Worst case:
T(n)=maximum time of algorithm of any input size of n.

Average case:
T(n)=expected time of algorithms overall inputs of size n.
Need assumptions of statistical distribution of inputs.

Best case:
Cheat with a slowly algorithm that works fast on some input.

Conclusions:

It is always O(nlogn), it is a very good alternative if the extra memory requirement is not a problem. Array elements with fast comparisons and slow copying seem to slightly penalize merge sort.
O(nlgn) grows more slowly than O(n2).
Therefore merge sort asymptotically beats insertion sort in the worst case.
In practice, merge sort beats insertion sort for n>30 or so.

ADT is the basic mathematical concept that defines the data type and stands for Abstract Data Type. Formally, ADT can be defined as a set of data values and the associated operations that are precisely specified, independent of any particular implementation.

Value Definition:
The Value definition defines the collection of values from the ADT and consists of two parts: A definition Clause (compulsory) and A Condition Clause (optional).

Operator Definition:
The operator definition consists of three parts: Header, Precondition and Post Condition.

An example of ADT.

abstract typedef <> STRING;

abstract length (s)
STRING s;
postcondition length = = len(s);

abstract STRING concat(s1,s2)
STRING s1,s2;
postcondition concat=s1+s2;

abstract STRING substr(s1, i, j)
STRING s1;
int i, j;
precondition 0 <= i < len(s);
0 <= j <= len(s1) – i;
postcondition substr = = sub(s1,i,j);

abstract pos(s1, s2)
STRING s1,s2;
postcondition

( ( pos = = -1) && (for( i=0; i <= lastpos; i++ ) (s2 <> sub(s1,i,,len(s2) ) ) ) )
| |
( ( pos >= 0) && ( pos <= lastpos) && ( s2 = = sub (str1, pos, len(s2) )

&& ( for( i=1; i sub(s1,i, len(s2) ) ) ) )

Contrary to popular belief, computers are not clever. Left to itself, a computer doesn’t do anything at all – it won’t show the time, or display what you type on the screen, let alone play a video game. The reason that computers are such useful tools, and give the appearance of cleverness, is that they follow instructions, very accurately, very repetitively, and very quickly. For example, when a computer displays a clock, it does so because it has instructions for how to draw every color and tick mark in the clock face, and every line in the clock’s rotating hands, onto the computer screen.

Programming is the act of giving instructions to a computer so that it knows how to perform an action. Fundamentally, these instructions are a series of numbers – to a computer, everything is numbers – in a kind of code where different numbers represent different instructions. The good news is that programmers don’t have to learn all these numbers (the ‘machine code’), because they can write their instructions in a more intuitive form, and then have the computer convert these instructions into machine code.

The intuitive or human-readable form of instructions is called a computer language. Like languages in the real world, there are dozens of computer languages. Some are for specialized tasks and others are more general-purpose. What all programming languages have in common is that they enable programmers to create instructions for a computer without having to learn the computer’s numeric machine code.

Author: Rich Tebb

Matthew Applegate, aka Pixelh8, is a leading light of the "chiptune" scene - music made using vintage home computers. Now he is embarking on his most ambitious project to date, holding two concerts consisting of music made on some of the oldest and rarest computers in the world at the UK's National Museum of Computing at Bletchley Park, the second world war code-breaking centre. Sumit Paul-Choudhury talked to him ahead of the performances of his show, called Obsolete?.

Listen to Chocolate Milk, from the album The Boy With The Digital Heart (2007, Hidden Youth Records UK)

Listen to Math, part of Pixelh8's new show Obsolete? (2009, Hidden Youth Records UK)

How did you get into this music?

I was in an REM covers band in the late 1990s, and the Amiga 500 I used to do our orchestration was fairly limited - it came out sounding like chiptunes. By comparison, modern PCs using samples have always sounded to me like they were trying too hard. They just didn't sound right.

When I realised that you could emulate old machines on a PC and learn what was going on inside them, I went back to the older sounds. I've designed instruments for pop stars. I reprogrammed Game Boys for UK artist Damon Albarn, for example, turning them into real musical instruments.

I grew out of the home computers and started to use scientific machines. With Obsolete? I've gone right back to the beginning of what computers can do in terms of sound. It's not just about sound chips, but the electromechanical sounds they make: the fans, the tape readers, the teleprinters - crunchy sounds.

What kind of music is it?

I usually do my own weird version of pop music in one-off songs, but this is a lot more elaborate. It's a concert work - a complete study of Bletchley Park, its history and its people, and of mathematics and code-breaking.

There are hidden codes and themes of encryption within the music. For example, I created a rhythm on the Colossus [the world's first programmable electronic computer]. The Colossus was used to break wartime codes: the Nazis enciphered Morse code messages by adding a second layer of Morse on top. I think of Morse codes as rhythms, so the piece has multiple rhythms overlaid.

There is also one piece of music where I'm going to put the date of the concert into a hand-wound adding machine and turn the handle. As it turns it will make a rhythm for that particular night. But it's not going to come out as some sort of strict mathematical, avant-garde modern music. It does have all these things in it, but it's still music.

How do you turn primitive computer sounds into music?

I make chiptune music and I do circuit-bending, too. Chiptunes are about reprogramming old computers and using their sound chips to make new music. I've had to learn all the relevant computer languages from the 1970s to 1994. In fact, the best chiptune musicians are programmers.

Circuit-bending is taking an electronic device and short-circuiting it to create completely different outcomes to whatever it would originally have done.

I think the people at Bletchley Park were expecting me to just make pop music using the sounds of the machines, but that would trivialise it. The museum curators initially took a little persuading because some of the machines are worth, say, £4 million, and I have blown up machines in the past. But I promised to be sensible with them. I'm using samples in the performances, because there's no way I could use all the machines - they wouldn't let me move them. But some of them will be live.

Who are your musical inspirations?

I don't actually listen to chiptune music. My inspiration is really people like Marvin Gaye. For this piece, though, I've gone to 20th-century composers such as Schönberg, Bartok and Cage, to see how they explore themes.

What's next?

There are a few individual machines I'd like to work with. One is the Whirlwind from 1951, arguably the first computer to produce sound. I'd also like to do more projects like Obsolete?, but in different areas, such as using machines that have a specific function - in astronomy, say. I got everybody scared when I said I'd like to work on strategic nuclear defence machines.

Listen to Chocolate Milk, from the album The Boy With The Digital Heart (2007, Hidden Youth Records UK)

Listen to Math, part of Pixelh8's new show Obsolete? (2009, Hidden Youth Records UK)

--
src:newscientist.com

--
www.aakarpost.com

Henny Youngman  - "When I told my doctor I couldn't afford an operation, he offered to touch-up my X-rays."

Edward Richardson, 41, was convicted of killing 26-year-old Sarah Richardson in a "frenzied and brutal attack" at her parents' home in Biddulph, Staffordshire, on May 12 last year.

Richardson, of Mayfield Road, Biddulph, was given a minimum term of 18 years in jail by a judge at Stafford Crown Court after a jury found him guilty of murder.

Fiona Cortese, from the Crown Prosecution Service, Staffordshire, said Richardson went to his in-laws' home, where his wife had been living since their separation in April 2008, after she failed to reply to his text messages following her change in status on social networking website Facebook.

She said: "Richardson became enraged when Sarah changed her marital status on Facebook to single and decided to go and see her as she was not responding to his messages.

"He gained entry by breaking the front door window and made his way into the property.

"Once inside he found Sarah in her bedroom and subjected her to a frenzied and brutal attack with a knife and then attempted to take his own life."

Mrs Richardson's parents, Beryl and Alan Boote, said their daughter's death had "devastated" the family.

In a statement released by police following Thursday's verdict, they said: "There simply aren't the words to describe how Sarah's death, and the awful way in which she died, has affected us. We all miss her so much.

"We're devastated and our lives will never be the way they were.

"It is important that we get justice for the taking of Sarah's life and we hope that Richardson will be an old man before he's ever allowed out of prison.

"Sarah was the loveliest daughter anyone could wish for. She was honest, loyal and sweet and everyone loved her.

"She loved all of her family to bits and to us she will always be precious and special."

Detective Inspector Andy Wall, from Staffordshire Police's Major Investigations Department, said: "She had decided that her marriage to Edward Richardson was over but this was clearly something he could not accept.

"The consequence was that Sarah lost her life in a brutal attack at her husband's hands in her family home.

"The verdict cannot bring Sarah back but we hope that it gives her family some form of comfort."

-----------------

telegraph.co.uk