Provided by Cognitive Sciences ePrint Archive
IJCSI International Journal of Computer Science Issues, Vol. 4, No. 2, 2009
25
ISSN (Online): 1694-0784
ISSN (Print): 1694-0814
The Folklore of Sorting Algorithms
Dr. Santosh Khamitkar1, Parag Bhalchandra2, Sakharam Lokhande 2, Nilesh Deshmukh2
School of Computational Sciences,
Swami Ramanand Teerth Marathwada University,
Nanded (MS ) 431605, India
Email : 1 [email protected] , 2 [email protected]
Abstract
The objective of this paper is to review the folklore knowledge
seen in research work devoted on synthesis, optimization, and
effectiveness of various sorting algorithms. We will examine
sorting algorithms in the folklore lines and try to discover the
tradeoffs between folklore and theorems. Finally, the folklore
knowledge on complexity values of the sorting algorithms will
be considered, verified and subsequently converged in to
theorems.
Key words: Folklore, Algorithm analysis, Sorting algorithm,
Computational Complexity notations.
1. Introduction
Folklore is the traditional beliefs, legend and customs,
current among people. Where as a theorem is a general
conclusion which has been proved [1].In view of these
definitions one might be tempted to conclude simply that
the folk theorem is a general conclusion which is
traditional and can be proved. The objective of this paper
is to narrate the folklore on complexity issues of sorting
algorithms and prove them. Accordingly, we shall attempt
to provide a reasonable definition for complexity or
criteria for folklore, followed by a detailed example
illustrating ideas. The letter endeavor might take one of
the two possible forms. We could take a piece of folklore
and show that it is a theorem or take a theorem and show
that it is folklore. Literature review in present context
highlights that the unified theory regarding their folklore
knowledge and in terms of theorems is found missing.
Since the dawn of computing, the sorting problem has
attracted a great deal of research. Till date, Sorting
algorithms are open problems and many researchers in
past have attempted to optimize them with optimal space
and time scale. Here Optimization was thought as the
process to reduce the time complexity so as to cross at
least O (n log n) milestone. Many new techniques were
proposed and till today fine refinement of them is in
progress. Every researcher attempted optimization in past
has found stuck to his / her observations regarding sorting
experiments and produced his/ her own results. Since
these results were specific to software and hardware
environment therein, we found abundance in the
complexity analysis which possibly could be thought as
the folklore knowledge. We tried to review this folklore
knowledge in past research work and came to a conclusion
that it was mainly devoted on synthesis, optimization,
effectiveness in working styles of various sorting
algorithms.
Our work is not mere commenting earlier work rather we
are putting the knowledge embedded in sorting folklore
with some different and interesting view so that students,
teachers and researchers can easily understand them.
Synthesis, in terms of folklore and theorems, hereupon
aims to check what past researchers have thought is really
the same they were saying and to analyze research on
sorting algorithms in such a way to get united
understanding of and support for the research results so
that they can be used directly and defended in public.
Since we have resolved to introduce no new technical
material in this paper except having technical elaboration
of folklore, and as researchers seem to be less familiar
with folklore than with theorems, we prefer to deal with
both approaches stated in above Para. We will present
strong evidence to the effect that a particular folk can be
converged in to theorem and vice versa. Folklore
knowledge on complexity values of the sorting
algorithms will be considered, verified and subsequently
converged in to theorems.
This paper is important as Sorting algorithms are often
prevalent in introductory computer science classes, where
the abundance of algorithms for the problem provides a
gentle introduction to a variety of core algorithm concepts.
Sorting algorithms illustrate a number of important
principles of algorithm design; some of them are also
counterintuitive [2]. Efficient sorting is important to
optimizing the use of other algorithms such as Binary
search and merge algorithms that require sorted lists to
IJCSI