Asked by
Manjit Kaur
in
Computers & Technology
at
2:14 PM on August 03, 2008
Mohd Saqib's Answer
Hello Manjit..
Source code
This program consists of three relations - mergesort, divide, and my_merge.
mergesort
This relation defines the actual merge sort. It actually states that the second argument is the result of sorting the first one.
First, the trivial cases are covered: Sorting an empty list of course gives the empty list again. Also, sorting a list with only a single element gives the list itself.
<<mergesort.pl>>=
mergesort ([], []).
mergesort([A], [A]).
If the list contains two or more elements, the sorted list is the merge of the results of sorting two lists containing half of the elements each.
<<mergesort.pl>>=
mergesort ([A, B | Rest], S) :-
divide([A, B | Rest], L1, L2),
mergesort(L1, S1),
mergesort(L2, S2),
my_merge(S1, S2, S).
[edit]
divide
This relation states that the second and third list are the result of dividing the first one. If the numbers of elements in the list to divide is odd, the extra element is added to the first resulting list.
Again, the cases of no or one element are easy: Dividing a list with no elements of course gives two lists with no elements each, while in the case of only one element, this is added to the first list.
<<mergesort.pl>>=
divide([] , [], []).
divide([A], [A], []).
If the unsplit list contains more than one element, the elements have to be distributed to both sublists. This is done here in the way one would do it e.g. with a deck of cards: The first card gets on the left heap, the second one on the right one, and the rest of the cards is distributed the same way. The effect is that the first sublist contains the odd-position elements of the original list, while the second one contains the even-position elements.
<<mergesort.pl>>=
divide([A , B | R], [A | Ra], [B | Rb]) :- divide(R, Ra, Rb).
my_merge
This relation states that the third list is a result of merging the first two while preserving the order. It is assumed that both lists to merge are already sorted.
If one of the lists is empty, obviously the merged list is equal to the other one.
<<mergesort.pl>>=
my_merge( A, [], A).
my_merge([], B, B).
In the general case, since the lists to merge are already sorted, the smallest element of each is the first one. Thus the absolutely smallest element is the smaller one of the first elements of both lists. The resulting list therefore consists of that element, followed by the result of merging the lists with that element removed.
<<mergesort.pl>>=
my_merge( [A | Ra], [B | Rb], [A | M]) :-
A =< B,
my_merge(Ra, [B | Rb], M).
my_merge([A | Ra], [B | Rb], [B | M]) :-
A > B,
my_merge([A | Ra], Rb, M).
For More Detail Refer..
http://en.literatep rograms.org/Merge_sort_(Prolog )
Answered at
3:21 PM on August 03, 2008
Read all answers
