Merge sort (Prolog)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

This article explains how to implement merge sort in Prolog.

Contents 1 Source code 1.1 mergesort 1.2 divide 1.3 my_merge 2 Execution result

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).

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).

Execution result

crypto@crypto ~/mergesort
$ prolog
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- ['mergesort.pl'].
% mergesort.pl compiled 0.00 sec, 2,176 bytes
Yes
?- divide([1, 2, 3, 4, 5, 6, 7], Odd, Even).
Odd = [1, 3, 5, 7]
Even = [2, 4, 6]
Yes
?- mergesort([3, 4, 8, 0, 1, 9, 5, 6], Sorted).
Sorted = [0, 1, 3, 4, 5, 6, 8, 9]
Yes
?-

Download code