DEV Community: Achyut Tripathi

Stack and Queue in Python

Achyut Tripathi — Mon, 10 Aug 2026 14:08:07 +0000

Have you ever wanted to eat at your favorite restaurant but saw a stack of books or had to wait in line? Every day, we come across things that resemble a stack and a queue. The most self-explanatory data structures are arguably stacks and queues; even so, they might be daunting to certain people.
In this note, we will discuss what stacks and queues are in the context of computer science, the operations we can carry out with them, and a small Python implementation of each.

Stack

A stack is a linear data structure with push and pop as its two primary operations. Push means to add anything to the top of the stack. Pop signifies the removal of an element from the stack's top. Due to its support for quick last-in, first-out (LIFO) semantics for inserts and deletes, stacks are referred to as a LIFO (Last in, First out) system. Typically, stacks do not permit random access to the things they contain, unlike lists or arrays.
Performance-wise, insert and delete operations on a proper stack implementation should take O(1) time.
Stacks can only be moved in one direction, so if we wanted to add anything to the structure or take something away, we would have to start from the top of the stack.
The stack's construction is identical to a stack of plates. When setting the table, we never begin by taking the very bottom plate; instead, we begin by making the plate from the top of the stack and placing it on the table. Newly washed dishes are placed at the top of the stack. In stacks, just the top of the stack may be used for insertion and deletion. This practice is known as Last In, First Out (LIFO).

Operations of Stack

A similar concept may be applied to the stack ADT to produce a collection of objects. It utilizes two main operations:

Pushing something up to the top of the stack
Removing a newly added item from a stack using a pop command
Getting the last element from the stack using the peek method.

The time complexity of a stack
push-O(1)
pop-O(1)
peek-O(1)

When are stacks useful?

Tracing back to access the previous elements- for instance, undo operations in editors are similar to popping a recently pushed code change from the stack of edit history. Similar to popping a website visit that was recently pushed into the history stack of a browser, back operations in browsers do the same thing.

How does create your own stack

class Stack:
    def __init__(self):
        self.stack = []    
    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.stack.pop()    
    def push(self,data):
        return self.stack.append(data)    
    def top(self):
        if self.is_empty():
            return None
        else:
            return self.stack[-1]  
    def is_empty(self):
        return self.len() == 0 
    def len(self):
        return len(self.stack)    
s = Stack()
s.push(5)   # s=[5]
s.push(4)   # s =[5,4]
s.push(6)   # s =[5,4,6]
s.push(9)   # s = [5,4,6,9]
s.push(1)   # s = [5,4,9,6,1]
s.push(2)   # s = [5,4,9.6,1,2]
print(s.top())  # top of the stack is 2
print(s.pop())  # poped element is 2
print(s.len())  #lenght of stack is 5

Output

Implementing stacks as arrays versus linked lists

Linked lists are frequently used in stack operations. They naturally lend themselves to functioning exactly like singly-linked lists since they can only "grow" in one way, allowing us to add and delete members from a single location.

Remember that the linked list contains a head node and that adding members to the beginning of the linked list has constant space-time complexity (O(1)). I love that! We can do that single action regardless of the size of our stack in roughly the same amount of time since we are just adding and deleting from the top (our head node).
Can we use arrays to implement a stack? Yes; however, arrays are static data structures, thus there is a disadvantage to this. A collection of data in memory with a defined size is known as a static data structure. However, there is no upper limit to the size of a stack; it can expand indefinitely!

When utilizing an array to construct a stack, things might become pretty nasty if we try to add more components to the stack than the array can hold.
Since the stack believes it can expand as big as it wants, it won't stop us from adding additional items, but the array won't have enough room to provide the new elements we are adding adequate memory. An overflowing stack is the result of everything! That's never a good thing. For instance, each shelf on our bookshelf can hold 10 books. We are constantly adding to our collection of books, which has outgrown our bookshelves.
Linked lists, on the other hand, are dynamic data structures. Their memory may change in size. A dynamic data structure may fluctuate in size and shape as well as the amount of memory it requires; therefore, it doesn't require a specific amount of memory to be set aside for it to exist. When a stack is implemented using a linked list, stack overflows are rather infrequent. That would only ever occur if we used up all of the available memory on our computers. If that were the case, we'd be dealing with a much worse issue (like a memory leak).
To summarise, many stacks are linked list implementations for the following reasons:

continuous complexity of space-time
the capacity to expand rapidly in size. ##Building up a stack It's fantastic that we now understand what a stack is, but how challenging is it to construct one? Happy news: In Python, creating a stack is surprisingly simple because of lists []. We can add and remove components from the bottom of the stack.

Output

Queue

Enqueue and dequeue are the two primary operations of a queue, which is a data structure. Enqueue: Add a component to the queue's end. Dequeue: Take an item out of the queue by moving it to the bottom. First in, first out (FIFO) is the term used to describe queues as a data structure. Queues normally do not permit random access to the items they hold, unlike lists or arrays.
Performance-wise, insert and delete operations on a well-implemented queue should take O(1) time.
An open-ended data structure is a queue. Data is always added to one end (enqueued), and removed from the other (dequeued). First In First Out (FIFO) approach is modified in this.
The primary distinction between a queue and a stack is that components in a queue are added to the bottom and removed from the top, but elements in a stack are added to the top and removed from the top in just one direction.
A line of patrons waiting to enter a restaurant is a prime illustration of a queue. Each new client enters the queue at the back. Always start serving the person in front of the queue. First in, first out policy refers to the practise of serving the first client in line.

Operations of Queue

Similarly, we can put a new item in the queue and remove from the front of the queue. There are two main queue operations:
Enqueue means to add a new item to the rear (end) of the queue.
Dequeue means to take the first thing out of line, or to serve the first person in line.

Time complexity of a stack

enqueue-O(1)
dequeue-O(1)

When are queues useful?

When you want to handle items as they come in one at a time, you utilize queues. Examples include processing hundreds of queries to a web server, printing several papers, and uploading a lot of photos.
Queues are used in a wide variety of algorithms, scheduling issues, and parallel programming issues. Breadth-first search (BFS) on a tree or graph data structure is a quick approach that uses a queue.

How to create your own Queue

class Queue:
    def __init__(self):
        self.queue = []    
    def enqueue(self,data):
        self.queue.insert(0,data)    
    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop()    
    def len(self):
        return len(self.queue)    
    def is_empty(self):
        return self.len() == 0
q = Queue()
q.enqueue(3)  # q = [3]
q.enqueue(4)  # q = [4,3]
q.enqueue(7)  # q = [7,4,3]
q.enqueue(1)  # q = [1,7,4,3]
q.enqueue(2)  # q = [2,1,7,4,3]
print(q.dequeue())
print(q.len())

Output

Implementing Queue as arrays versus linked list

As we already know, when more components are put onto the stack than the allotted size of the array can support, implementing a stack as an array can lead to a messy stack overflow. Accordingly, it turns out that, depending on the circumstances and conditions, arrays may wind up being even poorer implementation tools when it comes to queues.
When we are aware of the size of our data structure in advance, arrays may be incredibly powerful. But there are several occasions when we are unsure of the size of the line. What transpires then when we need to add (enqueue) an element to a queue? In other words, if we are utilizing an array and do not know the queue size in advance, we will exhaust the memory and space that has been allocated. Therefore, we must duplicate the information in our array, then set aside more room and memory, and finally enqueue a new element at the end of the queue.
With array-based queue implementations, there is an additional layer of complexity because we enqueue (add) at the back of the array and dequeue (remove) from the front. While this isn't always a bad thing because accessing the first or last element in an array doesn't take too long, it isn't as convenient as with stacks, where adding and removing items all take place from one end of the structure. We will need to be able to reach both ends of our expanding array, which will increase the space-time complexity.
Things are made easier with a linked list implementation of a queue. Since memory can be spread and the linked list may expand dynamically (so long as we don't use up all of the computer's memory), we don't need to worry about the queue size in advance. Because we can easily locate a memory area and add a node with information about its next neighbor, enqueuing and dequeuing are easier to handle. There's no need to duplicate our queue, as we would have to if we were using an array approach. Additionally, if we add pointer references to the start and end of our list, we may enqueue or dequeue one element without having to go through the entire structure.
The space-time complexity of the enqueue and dequeue functions on a queue becomes constant time, or O(1), once the requirement to traverse through the queue is removed. This means that, regardless of the size of the queue, adding or removing an element always takes a fixed amount of time.

Building up a Queue

queue = [3,4,3,7,1,8,4,3,2]
queue.append(9) # 9 is added to the queue
print(queue)
queue.pop() # remove the first element from the queue. 
print(queue)

Output

Conclusion

We studied the most basic concepts of stack and queue in this note. We were familiar with how to use queues and stacks in Python. Both a stack and a queue can be implemented validly in array or linked list form. But it's crucial to understand how these two implementations differ from one another and when one could be more practical for us.
Two essential Python data structures that are frequently used for effectively managing and organizing data are stack and queue. A queue adheres to the FIFO (First In, First Out) philosophy, whereas a stack follows the LIFO (Last In, First Out) idea. Comprehending these ideas facilitates the resolution of programming issues and the creation of effective algorithms.
Lists and collections are two of the techniques that Python offers to build a stack and a queue. deque module. Developers can enhance their applications' performance, readability, and efficiency by selecting the right data structure based on the needs of an issue. Therefore, anyone studying Python and data structures must have a solid grasp of stacks and queues.

DDL(Data Definition Language) Statements in PostgreSQL

Achyut Tripathi — Mon, 10 Aug 2026 06:26:24 +0000

In PostgreSQL, objects including users, virtual warehouses, databases, schemas, tables, views, columns, functions, and stored procedures are created, modified, and altered using Data Definition Language (DDL) commands.
A collection of SQL commands called Data Definition Language (DDL) is used in PostgreSQL to specify and control the structure of database objects. DDL statements mostly deal with the creation, modification, and removal of objects like tables, databases, schemas, views, and indexes, in contrast to commands that work with the data stored in tables.
Several DDL statements, such as CREATE, ALTER, DROP, and TRUNCATE, are available in PostgreSQL. These commands assist database administrators and developers in creating the database structure, making changes to already-existing objects, and deleting objects or their contents when necessary. To effectively manage a PostgreSQL database's structure and organization, one must comprehend DDL statements.

PostgreSQL Create Table

To add a new table to a database in PostgreSQL, use the CREATE TABLE statement. A table uses rows and columns to hold data, with each row denoting a single record and each column defining a particular kind of information.
Column names, data types, and constraints like PRIMARY KEY, NOT NULL, UNIQUE, and DEFAULT can all be specified using the CREATE TABLE statement. In addition to ensuring that the table structure satisfies the application's needs, defining these components at table creation aids in maintaining data consistency.
To build a table with its columns and data types, use the create a statement. The fundamental syntax for creating a table is shown below.

Syntax:-

CREATE TABLE <table_name>(
<Column1> <DataType>,
<Column2> <DataType>,
<Column3> <DataType>,
<Column4> <DataType>,
.
.
.
<Column n> <DataType>
)

As you can see, we specified the table name after CREATE TABLE, followed by the column name and datatype in parentheses. Here is an example of how to make a table.

CREATE TABLE Student_Report(
   ID INT PRIMARY KEY     NOT NULL,
   SNAME           TEXT    NOT NULL,
   SAGE            INT     NOT NULL,
   SADDRESS        CHAR(50)
);

Output-

As you can see, we are creating the table Student_Report in the example above.We have four columns with the names ID, SNAME, SAGE, and SADDRESS, with ID serving as the main key and being both unique and non-null.

Let's set up another table.

CREATE TABLE Employee_Report(
   EID INT PRIMARY KEY     NOT NULL,
   ENAME           TEXT    NOT NULL,
   EAGE            INT     NOT NULL,
   EADDRESS        CHAR(50),
   ESALARY         INT
);

Output-

As you can see, we are creating the table Employee_Report in the example above.We have five columns with the names EID,ENAME,EAGE,EADDRESS, and ESALARY, with EID serving as the main key and being both unique and non-null.

\d Command in Postgres

The \d command, which will be used to list down all the tables in an associated database, may be used to check whether your table has been correctly constructed.

Syntax:-

\d

Example:-

postgres=# \d

Output-

In my system, 17 tables have been formed, but when you build the first two tables(which can be shown above) and run the query (\d), you can see the tables you've generated. You can view the table names for the student_report and Employee_Report tables here also.

“\d tablename” Command in Postgres

Syntax:-

\d tablename

Use “\d tablename” to specifically specify each table.

Example:-

postgres=# \d student_report

This command displays all of the student_report's details.

Output-

Exapmple-

postgres=# \d Employee_Report

This command displays all of the Employee_Report details.

Output-

PostgreSQL Drop Table

An existing table can be permanently removed from a database using PostgreSQL's DROP TABLE statement. It removes the table, all of the data it contains, and the table structure that goes with it. As a result, this command should be used with caution, particularly when handling production or sensitive data.

In order to prevent problems when the requested table does not exist, PostgreSQL also offers options like IF EXISTS. When a table is no longer needed or when a database structure needs to be entirely erased and rebuilt, the DROP TABLE statement can be helpful.
A table may be deleted from a database, a database can be removed, etc. using the drop command. The syntax and an example are provided below.

Syntax:-

DROP TABLE <table_name/database_name>

The drop command is used to drop or remove the table from the database and drop the database from the system.

Example:-

postgres=# drop table student_report;

This command drop the table student_report from the database.

Output:-

PostgreSQL Alter Table

In PostgreSQL, you can change an existing table's structure without erasing the table or its contents by using the ALTER TABLE query. As database requirements change, you can modify columns, constraints, and other table attributes.
You can rename tables or columns, add or remove constraints, and add, change, or remove columns using ALTER TABLE. Because of this, it is a crucial DDL statement for effectively updating and maintaining the database structure.
The Alter statement is used to make changes to the table structure, such as modifying a column's data type, name, or both. The syntax and an example of adding a column are shown below.

Syntax:-

ALTER TABLE <table_name>
<ADD/DROP/ALTER/ALTER> COLUMN <column_name> <datatype>

By using alter command you can add a column, modify a column, drop a column, rename a column.

Add columns in table using Alter

Syntax:-

ALTER TABLE <table_name>
<ADD> COLUMN <column_name> <datatype>

By using alter command you can add a column.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   ADD Bounus int;

In this PostgreSQL ALTER TABLE demonstration, the Employee_Report table will add a Bonus field. It will be a NULL column when it is created.

Output:-

Add multiple columns in table using Alter

Syntax:-

ALTER TABLE <table_name>
<ADD/DROP/ALTER/ALTER> COLUMN <column_name> <datatype>
<ADD/DROP/ALTER/ALTER> COLUMN <column_name> <datatype>
<ADD/DROP/ALTER/ALTER> COLUMN <column_name> <datatype>
......
;

When using the ALTER TABLE command in PostgreSQL, the following syntax is used to add additional columns to a table.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   ADD joining_date Date,
postgres-#   ADD Father_name char(20);

In this PostgreSQL ALTER TABLE demonstration, the Employee_Report table will add a joining_date and Father_name field. It will be a NULL column when it is created.

Output:-

Drop columns in table using Alter

Syntax:-

ALTER TABLE <table_name>
<DROP> COLUMN <column_name>

By using this alter command you can drop a column.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   Drop column joining_date;

In this PostgreSQL ALTER TABLE demonstration, the Employee_Report table will drop a joining_date field.

Output:-

Modify columns in table using Alter

Syntax:-

ALTER TABLE <table_name>
        ALTER COLUMN <column_name> TYPE <data_type>

By using this alter command you can Modify the column data type in the table.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   Alter column EADDRESS TYPE char(20);

In this PostgreSQL ALTER TABLE demonstration, the Employee_Report table will Modify the Column EADDRESS data type to char.

Output:-

Rename columns in table using Alter

Syntax:-

ALTER TABLE <table_name>
        RENAME COLUMN <old_name> TO <new_name>

When using this ALTER TABLE query in PostgreSQL, this syntax is to rename a column in a table.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   Rename column EADDRESS to HOMEADDRESS;

In this PostgreSQL ALTER TABLE QUERY, the Employee_Report table will Rename the Column EADDRESS to ADDRESS.

Output:-

Rename Table in table using Alter

Syntax:-

ALTER TABLE <table_name>
        RENAME TO <new_name>

When using this ALTER TABLE query in PostgreSQL, this syntax is to rename the table to a new table_name.

Example:-

postgres=# ALTER TABLE Employee_Report
postgres-#   Rename TO Employee_describe;

In this PostgreSQL ALTER TABLE QUERY, the Employee_Report table will be Rename to Employee_describe.

Output:-

PostgreSQL Truncate Table

To swiftly eliminate every row from an existing database while maintaining the table structure, use PostgreSQL's TRUNCATE database command. The table can still be utilized to store fresh data because TRUNCATE does not remove the table itself, in contrast to the DROP TABLE statement.

Because TRUNCATE TABLE is particularly made to clear an entire table, it is typically faster than using DELETE to remove all entries. Additionally, PostgreSQL offers options like CASCADE to truncate connected tables when needed and RESTART IDENTITY to reset associated sequence values.
TRUNCATE swiftly eliminates every row from a collection of tables. Although it is quicker since it does not really scan the tables, it has the same impact on each table as an unqualified DELETE. Additionally, it immediately frees up disc space rather than requiring a future VACUUM procedure. This works best with large tables.

Syntax:-

TRUNCATE TABLE <table_name>

With no changes to the table's structure, the TRUNCATE TABLE command eliminates all data from the table.

Example:-

postgres=# TRUNCATE TABLE Employee_describe;

The Employee_describe table's whole contents are removed using the TRUNCATE TABLE command in the example above.

Output:-

Truncate data over multiple table

You must separate each table with a comma (,) if you want to delete all the data from multiple tables at once.

Syntax:-

TRUNCATE TABLE
 <table_name>,
 <table_name>,
 <table_name>,
 ......;

With no changes to the table's structure, the TRUNCATE TABLE command eliminates all data from the multiple table.

Example:-

postgres=# TRUNCATE student_report,Employee_describe;

The Employee_describe table and student_report table , whole contents are removed using the TRUNCATE TABLE command in the example above.

Output:-

Conclusion

A PostgreSQL database's structure must be defined and managed using DDL (Data Definition Language) statements. There are several ways to create, alter, remove, and clear database objects and their data using commands like CREATE TABLE, ALTER TABLE, DROP TABLE, and TRUNCATE TABLE.
Developers and database managers can maintain an effective and well-organized database structure by comprehending these statements. PostgreSQL databases can be efficiently handled while preserving data consistency and integrity by utilizing the proper DDL command according to the demand.
All things considered, PostgreSQL DDL statements serve as the basis for creating and managing database schemas. By adding new columns, changing current constraints, or eliminating superfluous tables and data, they make it simpler to modify the database structure when application requirements change. Maintaining database structures' flexibility, organization, and suitability for long-term usage requires a thorough understanding of these procedures.
The DDL (Data Definition Language) Statements in PostgreSQL are covered in this tip. We are taught how to build, drop, and amend tables in PostgreSQL. When altering a table, we are shown how to add columns, change the datatype of columns, rename columns and tables, and lastly, we are taught how to use the PostgreSQL truncate command.

Next Steps

Normalization in SQL

Achyut Tripathi — Sun, 09 Aug 2026 13:31:33 +0000

In a database, if the tables are unnormalised, then there are many problems like Insertion anomalies, Deletion anomalies, update anomalies, and data redundancy. So we need to normalise the data by using different types of normal forms.
The process of structuring the data in the database is called normalisation. To reduce duplication from a connection or set of relations, normalisation is utilised. It is also utilised to eliminate undesired traits, including deletion, update, and insertion-related anomalies.
The bigger table is split into smaller tables during normalisation, and these tables are connected through relationships. Redundancy in the database table is reduced by using the normal form.
In relational databases, normalization is a database design approach used to efficiently arrange data and minimize redundancy. Large tables are broken up into smaller, related tables, and keys are used to create relationships between them. This procedure facilitates database maintenance, enhances data integrity, and helps remove duplicate data.
A set of guidelines called Normal Forms (NF), which include the First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), and higher normal forms, are used to carry out normalization. By adhering to these guidelines, developers can ensure data consistency and reduce storage needs while creating well-structured databases that are simpler to maintain, update, and query.

Problem with an unnormalized database

There are four types of anomalies (problems) with the database, and to remove those anomalies, Normaliztion is happened.
Anomalies are-

Insertion anomalies
Deletion anomalies
Updation anomalies
Data redundancy

Insertion anomalies

When a database architecture makes it impossible to add new data without including extraneous or irrelevant information, this is known as an insertion anomaly. This issue typically occurs in tables with redundant data that are poorly designed. As a result, in order to create a new record, users might have to submit redundant or insufficient information. By grouping data into distinct, related tables, normalization helps remove insertion anomalies and improves the accuracy and efficiency of data entry.
When some characteristics cannot be entered into the database without the presence of other attributes, this is known as an insertion anomaly.

Example

Example to show Insertion Anomalies-

In the database, there are five fields: Course Number, Tutor, Room, Capacity of room (students), and Limit.
And there are two entries in the table; the first tutor is Achyut, and the other is Kirti, with room numbers 101 and 102 respectively.
If we try to insert room-103 in the database. The data is not inserted in the table because there is no assigned tutor or course Number along with that room number, so that is called an insertion anomaly.

Deletion anomalies

When deleting a record from a table inadvertently erases other important data, this is known as a deletion anomaly. When different kinds of data are kept in the same table in poorly constructed databases, this issue typically occurs. Therefore, removing one piece of information may result in the loss of linked information that ought to have been kept. By dividing data into related, well-structured tables, normalization aids in the prevention of deletion anomalies.
When certain attributes are lost as a result of the deletion of other attributes, this is known as a deletion anomaly.

Example

In the above table, we deleted Course number 2, so along with the course number, we lost the whole row; we lost the room size and limit. So, that is called insertion anomalies.

Updation anomalies

An update anomaly occurs when the same data is stored in numerous rows and must be updated several times. If all events are not updated regularly, the database may contain inaccurate or inconsistent data. This problem often arises in improperly created tables with redundant data. Normalization helps eliminate update anomalies by reducing data duplication and organizing data into related tables.
An updation anomaly exists when one or more than one instances of duplicated data are updated, but not all.

Example

In the above table, if we update the first row of the capacity of the room by 70, and do not update the 3rd row of the same room. then that is called an updating anomaly.

In the 3rd row, there is an update anomaly.

Data Redundancy

The needless duplication of the same data in several locations within a database is referred to as data redundancy. Excessive duplication raises storage needs and can result in inconsistencies, update failures, and data anomalies, even tho some redundancy may be purposeful for performance reasons. By grouping data into distinct, related tables, normalization ensures that each item of data is kept only once and is preserved effectively, hence reducing data redundancy.
Data redundancy is the storage of the identical piece of information or data more than once in a database.

Example

If we add more than one phone number of the same person, like achyut then we create one more row and repeat all the same; then that is called data redundancy.

Data Redundancy Problem

Redundant data consumes a lot of additional disk space.
It takes more time to update duplicate data, which might cause a serious performance problem.

Normal Forms

A set of guidelines called Normal Forms (NFs) is used in database normalization to effectively arrange data and cut down on repetition. Each normal form enhances a database's structure and deals with particular kinds of data abnormalities. First Normal Form (1NF), Second Normal Form (2NF), and Third Normal Form (3NF) are the most widely utilized normal forms; higher normal forms offer more optimization. Applying these guidelines helps develop well-structured databases that assure data integrity, consistency, and easy maintenance.
There are 6 normal forms defined-

1st Normal form (1NF)
2nd Normal form(2NF)
3rd Normal form(3NF)
Boyce-Codd Normal form(BCNF)
4th Normal form(4NF)
5th Normal forn(5NF) All three anomalies (insertion anomaly, deletion anomaly, and update anomaly) are removed by the normal forms, but the 4th anomaly, which is data redundancy, is not completely removed by any of the normal forms; we can only minimize the data redundancy from the table, but not completely removed.

1st Normal form (1NF)

Example

This table has all the attribute is atomic(Unique) in nature, and there is no multivalued attribute in the table; then the table is in 1st normal form.

2nd Normal form (2NF)

The normalization process begins with the First Normal Form (1NF). A table is said to be in 1NF if there are no repeating groups or multiple values stored in a single column, each row is unique, and each column only contains atomic (indivisible) values. Data organization is enhanced, querying is made easier, and higher normal forms like 2NF and 3NF are made possible by converting a table to 1NF.
Certain non-key columns in a table that is not in 2NF might rely on a subset of the composite primary key instead of the entire key. In addition to producing redundant data, this may result in abnormalities in insertion, updating, and deletion. The database is made more efficient and well-organized by dividing partially dependent attributes into separate tables and creating appropriate associations.
By using 2NF, data redundancy is decreased, data integrity is enhanced, and database maintenance is made simpler. It guarantees that every non-key attribute fully characterizes the primary key, making the database design clearer and providing a solid basis for switching to Third Normal Form (3NF).
A relation is said to be in 2NF if there does not exist any partial functional dependency.
Partial Function Dependency- If a non-prime attribute of the relation depends upon the prime attribute of the relation, then a partial function dependency occurs.

3rd Normal form (3NF)

A relation is said to be in 3NF if all non-prime characteristics depend directly (non-transitively) on the relation's primary key.
If the Functional dependency is like (key -> non-prime attribute), then for Relation is satisfy for 3rd normal form; either x is the key or y is a prime attribute.
The third phase of database normalization is known as the Third Normal Form (3NF). If a table is already in 2NF and every non-key attribute depends only on the main key and not on any other non-key attribute, it is in 3NF. Transitive dependencies, in which one non-key column depends on another non-key column, are eliminated as a result.
Reducing data redundancy and preventing insertion, update, and deletion anomalies are the primary goals of 3NF. The database is made more structured, consistent, and manageable by dividing attributes that are not directly dependent on the primary key into the proper tables.

Boyce-Codd Normal Form (BCNF)

A relation is said to be in BCNF if the determinant is a key. BCNF is the strongest form of 3NF.
For example, if the Functional dependency is like (x -> y), then for Relation is satisfy BCNF, x must be a key.
Compared to the Third Normal Form (3NF), the Boyce-Codd Normal Form (BCNF) is a more stringent type of database normalization. If the determinant is a candidate key for each functional dependency, the table is in BCNF. To put it simply, any attribute that influences another property needs to be able to uniquely identify a record.
Even after applying 3NF, a table may still have some kinds of redundancy and abnormalities, which BCNF helps remove. Database designers can enhance data consistency, integrity, and overall database structure by breaking down tables that violate BCNF into smaller, linked tables.

4th Normal Form (4NF)

A relation with trivial multivalued dependency is called 4th normal form.
If (x->->y) is non-trivial, then x must be a key for having the 4th normal form.
Multivalued dependency - When two attributes in a table are independent of one another yet both depend on a third attribute, the situation is known as multivalued dependence.
An enhanced level of database normalization that addresses multivalued relationships is called the Fourth Normal Form (4NF). Unless the determinant is a superkey, a table is in 4NF if it is already in BCNF and has no non-trivial multivalued dependencies. To put it simply, 4NF makes sure that separate sets of multiple-valued data aren't needlessly kept in the same database.

Reducing data redundancy and preventing insertion, update, and deletion anomalies brought on by multivalued relationships are the primary goals of 4NF. 4NF produces a more organized and effective database structure by dividing independent multi-valued attributes into distinct tables.

5th Normal form (5NF)

A relation is in 5th normal form if it is in 4NF and cannot be further decomposed.If a relation is in 4NF, lacks join dependencies, and requires lossless joining, it is in 5NF.
The Fourth Normal Form (4NF) is an advanced level of database normalization that deals with multivalued dependencies. A table is in 4NF if it is already in BCNF and does not contain any non-trivial multivalued dependencies unless the determinant is a superkey. In simple terms, 4NF ensures that independent sets of multiple-valued information are not unnecessarily stored together in the same table.
The main purpose of 4NF is to reduce data redundancy and prevent insertion, update, and deletion anomalies caused by multivalued relationships. By separating independent multi-valued attributes into different tables, 4NF creates a cleaner and more efficient database structure.

Conclusion

In SQL, normalization is a crucial database design method that promotes effective data organization, minimizes redundancy, and preserves data integrity. Normalization reduces insertion, deletion, and update anomalies while simplifying database management and upkeep by organizing data into relevant and well-structured tables.
The main normal forms—1NF, 2NF, 3NF, BCNF, 4NF, and 5NF—were examined in this article. Each normal form offers a more structured database structure by addressing particular kinds of dependencies and redundancies. Developers can create dependable, consistent, and effective relational databases by comprehending these common forms.
Higher levels of normalization may necessitate more tables and joins even tho they can offer better data structure. As a result, the data structure, performance requirements, and application requirements should all be taken into consideration when choosing the proper amount of normalization.

Next Steps

PostgreSQL Joins

Achyut Tripathi — Sun, 09 Aug 2026 09:25:34 +0000

This PostgreSQL Tip provides syntax and examples to help users understand how to implement PostgreSQL JOINS (inner and outer).

Data is frequently spread across several tables while dealing with relational databases in order to reduce redundancy and enhance data management. However, merging data from several related tables is typically necessary to obtain significant information. PostgreSQL joins become crucial in this situation.

You can combine rows from two or more tables based on a related column using a variety of join types offered by PostgreSQL. Joins provide a strong and effective method of querying relational data, whether you need to get matching records, include mismatched rows, or compare data between databases.

This article will explain PostgreSQL joins, their significance, and how to use various join types, such as INNER JOIN, LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN, CROSS JOIN, and SELF JOIN. To help you utilize joins with confidence in real-world PostgreSQL applications, we'll walk you through each join's straightforward syntax, useful examples, and anticipated results.

The problem we have when accessing data from various tables based on logical relationships between them is the goal of JOINs in SQL. Data from database tables is fetched using JOINS, which then represents the resulting dataset as a different table.

PostgreSQL Joins

Data from two or more tables can be combined in a database using the PostgreSQL joins clause. The following list of PostgreSQL types:

The cross join
The inner join
The left outer join
The right outer join
The full outer join

Create Initial Tables

Let's take into account the two tables for the joins.

Company Table
Department Table

Company Table

Let’s make the Company Table

CREATE TABLE COMPANY(
   ID INT PRIMARY KEY     NOT NULL,
   NAME           CHAR(20),
   AGE            INT     NOT NULL,
   ADDRESS        CHAR(50),
   SALARY         INT,
   JOIN_DATE      DATE
);

Step 1: Create the Table

CREATE TABLE COMPANY

Creates a new table named COMPANY.

Step 2: Define the Columns

1.

sql ID INT PRIMARY KEY NOT NULL

Unique employee ID; cannot be empty.
2.

sql NAME CHAR(20)

Stores the employee's name (up to 20 characters).
3.

sql AGE INT NOT NULL

Stores the employee's age; cannot be empty.
4.

sql ADDRESS CHAR(50)

Stores the employee's address.
5.

sql SALARY INT

Stores the employee's salary.
6.

sql JOIN_DATE DATE

Stores the employee's joining date.

Step 3: Result

A COMPANY table is created with six columns to store employee details.

Output-

Inserting data

Let’s insert data into the COMPANY table

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (1, 'Achyut', 20, 'Gorakhpur', 30500.00,'2022-10-29');
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (2, 'Neha', 22, 'Banaras', 40500.00,'2022-12-15');

INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (3, 'Kirti', 26, 'Lucknow', 50500.00,'2022-08-03');
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (4, 'Ankit', 27, 'Delhi', 60500.00,'2022-02-19');
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (5, 'Ankur', 30, 'Goa', 70500.00,'2022-08-27');
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (6, 'Pallavi', 34, 'Jaipur', 80500.00,'2022-04-22');
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY,JOIN_DATE) VALUES (7, 'Radha', 36, 'Bali', 90500.00,'2022-01-26');

After successfully inserting all the data, let’s see the data

select * from company;

Output-

Department Table

Let’s make a Department Table

CREATE TABLE DEPARTMENT(
   ID INT PRIMARY KEY NOT NULL,
   DEPT CHAR(40),
   EMP_ID INT NOT NULL
);

Step 1: Create the Table

CREATE TABLE DEPARTMENT

Creates a new table named DEPARTMENT.

Step 2: Define the Columns

1.

sql ID INT PRIMARY KEY NOT NULL

Unique department record ID; cannot be empty.
2.

sql DEPT CHAR(40)

Stores the department name (up to 40 characters).
3.

sql EMP_ID INT NOT NULL

Stores the employee ID associated with the department; cannot be empty.

Step 3: Result

A DEPARTMENT table is created with three columns to store department information and the corresponding employee ID.

Output-

Inserting Data

Let’s insert data into the Department table

INSERT INTO Department(ID,DEPT,EMP_ID) VALUES (1,'IT',1);
INSERT INTO Department(ID,DEPT,EMP_ID) VALUES (2,'SALES',2);
INSERT INTO Department(ID,DEPT,EMP_ID) VALUES (3,'SDE',6);

After successfully inserting all the data let’s see the data

select * from Department;

Output-

THE CROSS JOIN

The PostgreSQL Cross Join is used to aggregate all potential results from several tables and to deliver the output, which includes each row from all the chosen tables. The Cartesian join, as it is sometimes known, enables the production of the Cartesian sum of all associated tables.

Every row from one table is combined with every entry from another table using a SQL join technique called a CROSS JOIN. It does not necessitate a matching condition between the tables, in contrast to other joins. The total number of rows in the result is therefore equal to the number of rows in the first table multiplied by the number of rows in the second table. This is known as the Cartesian product.

While you need to generate every possible combination of records—for example, while developing product variations, scheduling combinations, or testing various data scenarios—CROSS JOIN comes in handy. However, it should be used carefully with large tables to prevent performance difficulties because it might generate a very large number of rows.

Syntax

SELECT <COLUMN NAME> FROM TABLE1 CROSS JOIN TABLE2;

Example

A cross-join operation between the company table and the department table will result in any feasible combination, like

Query

SELECT EMP_ID, NAME, DEPT FROM COMPANY CROSS JOIN DEPARTMENT;

retrieves the EMP_ID, NAME, and DEPT columns by performing a CROSS JOIN between the COMPANY and DEPARTMENT tables. A CROSS JOIN combines every row from the COMPANY table with every row from the DEPARTMENT table, creating all possible combinations of records. Since no join condition is specified, the result is the Cartesian product of both tables.

Output

It will produce the following result.

THE INNER JOIN

The INNER JOIN keyword in PostgreSQL selects all rows from both tables if the criteria is met. INNER JOIN keyword will combine all rows from both tables whose conditions, i.e., the common field's value, are met to produce the result set.
One of the most popular SQL join operations is an INNER JOIN. Based on a matched value in a linked column, it merges rows from two or more tables. Non-matching rows are not included in the result; only records with matching values in both tables are. Working with relational databases requires an understanding of INNER JOIN, which is frequently used to obtain relevant data from several tables.

Syntax

SELECT <Column_name> FROM table1 INNER JOIN table2 ON table1.column=table2.column;

Query

SELECT EMP_ID, NAME, DEPT FROM COMPANY INNER JOIN DEPARTMENT ON COMPANY.ID=DEPARTMENT.EMP_ID;

retrieves the EMP_ID, NAME, and DEPT columns by performing an INNER JOIN between the COMPANY and DEPARTMENT tables. The ON COMPANY.ID = DEPARTMENT.EMP_ID condition matches each employee in the COMPANY table with the corresponding department in the DEPARTMENT table. Only the records with matching IDs in both tables are included in the result, while non-matching records are excluded.

Output

It will produce the following result.

THE LEFT OUTER JOIN

All rows from the left table and all rows from the other table that satisfy the join criteria specified in the ON condition are returned using the PostgreSQL LEFT JOIN or Left Outer Join. It will return null if no matching entries were located in the appropriate table.
All records from the left table and the matching records from the right table are returned via a SQL join operation known as an LEFT OUTER JOIN, or LEFT JOIN. The row from the left table is still included in the result with NULL values for the right table's columns if there is no matching record in the right table. When retrieving all data from one dataset while incorporating relevant data from another table whenever it is available, the LEFT OUTER JOIN is frequently utilized.

Syntax

SELECT columns FROM table1 LEFT OUTER JOIN table2 ON table1.column = table2.column;

Query

SELECT columns FROM table1 LEFT OUTER JOIN table2 ON table1.column = table2.column;

uses an LEFT OUTER JOIN between tables 1 and 2 to get data. Based on the given join condition, it retrieves every record from the left table (table 1) and the corresponding records from the right table (table 2). The row from the left table is still included in the result with NULL values for the right table's columns if there is no matching record in the right table.

Output

It will produce the following result.

THE RIGHT OUTER JOIN

To retrieve all rows from the right table and rows from the other table when the join requirement is satisfied, as stated in the ON condition, PostgreSQL's RIGHT JOIN, or Right Outer Join, is utilised. It will return null if no comparable records from the left table were located.
An SQL join technique known as a RIGHT OUTER JOIN (or RIGHT JOIN) yields all of the records from the right table along with the corresponding records from the left table. The result still contains the entry from the right table with NULL values for the left table's columns if there is no matching record in the left table. When retrieving all of the data from the right table and adding relevant data from the left table once a match is found, the RIGHT OUTER JOIN is helpful.

Syntax

SELECT columns FROM table1 RIGHT OUTER JOIN table2 ON table1.column = table2.column;

Query

SELECT EMP_ID, NAME, DEPT FROM COMPANY RIGHT OUTER JOIN DEPARTMENT ON COMPANY.ID=DEPARTMENT.EMP_ID;

uses a RIGHT OUTER JOIN between the COMPANY and DEPARTMENT tables to retrieve the EMP_ID, NAME, and DEPT columns. Based on the criteria COMPANY.ID = DEPARTMENT.EMP_ID, it retrieves every entry from the DEPARTMENT table and the corresponding entries from the COMPANY table. The result still includes a department with NULL values for the columns from the COMPANY table if there isn't a corresponding employe.

Output

It will produce the following result.

THE FULL OUTER JOIN

An inner join is executed first. Then, a joined row is inserted with null values in columns of table T2 for each record in table T1 that does not meet the join criteria with any row in table T2. Additionally, a joined row with null values in the columns of T1 is added for each row of T2 that does not meet the join criteria with any row in T1.
A SQL join operation that returns every record from both tables is called a FULL OUTER JOIN, or FULL JOIN. The information is merged into a single row when a matching record is found. The entry from either table is still included in the result if there is no match, but the missing columns have NULL values. When you wish to retrieve every record from both tables, regardless of whether a matching value exists, FULL OUTER JOIN is helpful.

Syntax

SELECT columns FROM table1 FULL OUTER JOIN table2 ON table1.column = table2.column;

Query

SELECT EMP_ID, NAME, DEPT FROM COMPANY FULL OUTER JOIN DEPARTMENT ON COMPANY.ID=DEPARTMENT.EMP_ID;

retrieves the EMP_ID, NAME, and DEPT columns by performing a FULL OUTER JOIN between the COMPANY and DEPARTMENT tables. It returns all records from both tables, matching rows based on the condition COMPANY.ID = DEPARTMENT.EMP_ID. If a record in either table has no matching record in the other table, it is still included in the result, with NULL values for the missing columns.

Output

It will produce the following result.

Conclusion

Use an inner join to display just data that matches from both tables. Use an outer join to display all the data from both tables, and a left outer join to display all the data from one table and just the data from the second table that matches the data in the first table.
One of PostgreSQL's most crucial features is SQL joins, which let you obtain and merge relevant data from several tables. Joins allow you to get comprehensive query results and establish meaningful relationships across tables without maintaining redundant data. Writing effective and precise SQL queries requires an understanding of how joins operate.
The various PostgreSQL join types—CROSS JOIN, INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN, and FULL OUTER JOIN—were examined in this article. Every join has a distinct function, such as producing every possible combination of records, obtaining only matching rows, or including unmatched data from one or both databases. Selecting the right join type guaranties that your results precisely satisfy the needs of your application and enhances query efficiency.
The various PostgreSQL join types—CROSS JOIN, INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN, and FULL OUTER JOIN—were examined in this article. Every join has a distinct function, such as producing every possible combination of records, obtaining only matching rows, or including unmatched data from one or both databases. Selecting the right join type guaranties that your results precisely satisfy the needs of your application and enhances query efficiency.

Next Steps

Merge Sort Algorithm in Python

Achyut Tripathi — Wed, 05 Aug 2026 18:57:43 +0000

Data we save or get from an application could occasionally be poorly or randomly organized. We might need to reorganize the data to handle or utilize it properly. To arrange data, computer scientists have developed a variety of sorting algorithms over time.
In this post, we'll examine the merge sort algorithm, provide an introduction to the divide-and-conquer strategy for addressing problems, explain its operations and principles, and implement it in Python. We'll also contrast how quickly it can sort a list of objects.
Based on the Divide and Conquer strategy, Merge Sort is one of the most effective and popular sorting algorithms. An unsorted array is recursively divided into smaller subarrays until each subarray has a single element. A fully sorted array is produced by merging these smaller subarrays back together in sorted order.
Merge Sort is a great option for sorting big datasets since it ensures a time complexity of O(n log n) in the best, average, and worst circumstances, unlike straightforward sorting algorithms like Bubble Sort or Selection Sort. Merge Sort needs more memory because it generates temporary arrays during the merging operation, but its reliable performance and stability make it a well-liked method in practical applications.
Recursion may be used to build Merge Sort in Python, making it an excellent illustration of divide-and-conquer tactics, recursive programming, and effective algorithm design. In order to help you grasp the algorithm, you will study how Merge Sort operates, comprehend how it is implemented in Python step-by-step, evaluate its time and space complexity, and witness a real-world application.

What Are Divide-and-Conquer Algorithms?

Divide-and-conquer methods can be applied recursively, meaning the main problem is broken down into related subproblems before being solved. The solutions to the smaller difficulties are combined to provide the overall solution to the bigger issue.
The divide-and-conquer method of algorithm design has three key parts:
Divide - continuously breaks down the larger problem into smaller subproblems.
Conquer - solves each subproblem by using any function.
Combine - merges all the solutions of each subproblem and makes a single unified solution, which becomes the solution to the starting problem.

What Is Merge Sort?

To efficiently sort the items in a list, the merge sort method uses the divide-and-conquer algorithm paradigm. The foundation of the merge sort process is to divide the list in half, then continually separate the new half into its individual parts. Following a comparison of each component separately, the combined results are combined to create the final sorted list.
Merge Sort is a comparison-based sorting algorithm that effectively sorts elements by using the Divide and Conquer strategy. Merge Sort continually splits the array into two smaller halves until each subarray has just one element, as opposed to sorting the entire array at once. The method then combines these subarrays back together in the proper sequence to create a fully sorted array because a single element has already been sorted.
With a time complexity of O(n log n) in the best, average, and worst scenarios, Merge Sort is renowned for its consistent performance. Additionally, it maintains the relative order of elements with equal values because it is a stable sorting algorithm. Due to its efficiency and dependability, Merge Sort is frequently used for sorting huge datasets, linked lists, and external data stored on drives, even if the merging procedure necessitates additional RAM.

Implementation of Merge Sort in Python

The merge sort method is implemented using a two-part strategy.
The split phase of the divide-and-conquer paradigm will be carried out in the first portion. This section's implementation of the code will separate the initial list into more manageable parts. Only when each separated component can no longer be broken down will the original list split come to an end.
An example of the algorithm's first step may be shown below.

Step 1: Top-to-Bottom Approach

def merge_sort(list):
    # 1. Store the length of the list in the length container.
    length = len(list)
    # 2. if length is equal to 1 then return original list.
    if length == 1:
        return list
    # 3. Identify the list midpoint and break the list into two part one is left part and second is right part.
    mid = length // 2
    # 4.A partitioned section of the list is supplied as an argument to the merge_sort function, which makes sure that each part is split into its individual parts.
    left_part = merge_sort(list[:mid])
    right_part = merge_sort(list[mid:])
    # 5. The merge_sort function produces a list with sorted left and right part as its output.
    return merge(left_part,right_part)

Step 1.1: Define the Merge Sort Function

def merge_sort(list):

The merge_sort() function, which accepts a list as input, is defined at this line. This function's goal is to use the Merge Sort algorithm to sort the list's elements.

Step 1.2: Find the Length of the List

length = len(list)

The total number of elements in the list is determined using the len() method. The length is kept in the length variable, which aids in figuring out whether the list has to be further divided.

Step 1.3: Check the Base Case

if length == 1: 
return list

The recursive algorithm's base case is this. The function just returns the list without making any more recursive calls if there is only one entry in the list, indicating that it has already been sorted.

Step 1.4: Find the Midpoint of the List

mid = length // 2

The list is split into two equal (or nearly equal) halves at the middle. By performing integer division, the // operator guarantees that the midpoint is always an integer.

Step 1.5: Divide the List into Two Halves

left_part = merge_sort(list[:mid]) 
right_part = merge_sort(list[mid:])

The list is divided into two smaller sublists:

list[:mid] creates the left half.
list[mid:] creates the right half.

The merge_sort() function is then called recursively on both halves. This process continues until every sublist contains only one element.

Step 1.6: Merge the Sorted Halves

return merge(left_part, right_part)

The left and right halves are already sorted when the recursive calls are complete. These two sorted halves are combined into a single sorted list using the merge() method.

Step 2: Bottom-to-Top Approach

# 1. take the two list as input and return the sorted list as output
def merge(left, right):
    # 2. Initialize an empty list as answer that will be store the sorted elements
    # Initialize two variables i and j which are used pointers when iterating through the lists.
    answer = []
    i = j = 0


    # 3. Executes the while loop if both pointers i and j are less than the length of the left and right lists
    while i < len(left) and j < len(right):
    # 4. Compare the elements at every position of both lists during each iteration
        if left[i] < right[j]:
            # 5. if the left list value less then right list value , then append the left list value in the answer.
            answer.append(left[i])
            # 6. increase or move the pointer by 1.
            i += 1
        else:
            #7. append the right list value in the answer if right list value is lesser then tha left list value.
            answer.append(right[j])
            #8. and move the j pointer by 1
            j += 1
    # 9. the remaining value of the both left and right list is picked from the current pointer to the end and extend to the answer
    answer.extend(left[i:])
    answer.extend(right[j:])
    #10.return the answer(that is sorted list)
    return answer

Step 2.1: Define the merge() Function

def merge(left, right):

The merge() function creates a single sorted list by combining two previously sorted lists (left and right) as input.

Step 2.2: Initialize Variables

answer = []
i = j = 0

The combined sorted elements are stored in an empty list called answer. The initial values of the two pointers, i and j, are 0. The current entry in the left list is tracked by pointer i, and the current element in the right list is tracked by pointer j.

Step 2.3: Compare Elements from Both Lists

while i < len(left) and j < len(right):

As long as both lists contain unprocessed elements, the while loop will continue. The algorithm compares the current elements that i and j point to on each iteration.

Step 2.4: Add the Smaller Element to the Result

if left[i] < right[j]:
    answer.append(left[i]) 
    i += 1 
else:
    answer.append(right[j])
    j += 1

The left pointer (i) advances to the following element if the current element in the left list is smaller and is added to the answer list. If not, the right pointer (j) is increased, and the current element from the right list is appended. This procedure guarantees that the components are included in the answer in the correct order.

Step 2.5: Append the Remaining Elements and Return the Result

answer.extend(left[i:]) 
answer.extend(right[j:])
return answer

The remaining items from the other list have already been sorted once one of the lists has finished processing. The extend() technique is used to add these components to the answer list. Lastly, the fully combined and sorted list is returned by the function.

Step 3: Create Input List Function

def merge_sort_print():
    input = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
    print(input)
    sorted_list = merge_sort(input)
    print(sorted_list)
merge_sort_print()

The Merge Sort algorithm's operation is illustrated via the merge_sort_print() function. Initially, an unsorted list of integers is created and printed to the console. The list is then sorted in ascending order using the merge_sort() function, and the outcome is saved in the sorted_list variable. You can compare the original and sorted outputs after it prints the sorted list. The function is executed, and the results are shown by the last statement, merge_sort_print().

Merge Sort Code In Python

Now that you know how the Merge Sort algorithm operates, let's put it into practice in Python. The input list is continuously divided into smaller sublists by the implementation using a recursive technique until each sublist has just one element. The final sorted list is created by merging the sorted sublists back together in the proper order when the division operation is finished.

The Merge Sort algorithm's full implementation is shown in the Python program that follows. It contains a merge() function to combine the sorted sublists into a single sorted list and a merge_sort() method to split the list recursively.

def merge_sort(list):
    length = len(list)
    if length == 1:
        return list
    mid = length // 2
    left_part = merge_sort(list[:mid])
    right_part = merge_sort(list[mid:])
    return merge(left_part, right_part)
def merge(left, right):
    answer = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            answer.append(left[i])
            i += 1
        else:
            answer.append(right[j])
            j += 1
    answer.extend(left[i:])
    answer.extend(right[j:])
    return answer
def merge_sort_print():
    input1 = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
    print(input1)
    sorted_list = merge_sort(input1)
    print(sorted_list)
merge_sort_print()

Step 1: Define the merge_sort() Function

The algorithm's primary function is merge_sort(). It initially determines the input list's length and verifies the base case. The function returns the list right away if there is only one element because it has already been sorted. If not, the midpoint is used to split the list in half.

def merge_sort(list): 
    length = len(list) 
    if length == 1: 
        return list 
    mid = length // 2 
    left_part = merge_sort(list[:mid]) 
    right_part = merge_sort(list[mid:])

Step 2: Recursively Divide the List

The function recursively calls itself for both the left and right half of the list. This method continues until every sublist has only one element. This is the Divide step in the Divide and Conquer method.

left_part = merge_sort(list[:mid]) 
right_part = merge_sort(list[mid:])

Step 3: Merge the Sorted Sublists

The merge() function merges the two parts into a single sorted list after they have been sorted. It adds the smaller element to a new list after comparing each element individually from the left and right sublists.

return merge(left_part, right_part)

The merge() function:

def merge(left, right):
    answer = []
    i = j = 0

uses two pointers (i and j) to traverse the left and right sublists efficiently.

Step 4: Add Remaining Elements

The extend() method is used to add any entries from the other sublist to the result after one of the sublists has finished processing. These components can be directly attached because they have already been sorted.

answer.extend(left[i:])
answer.extend(right[j:])
return answer

Step 5: Execute the Program

An unsorted list is created, shown, sorted using the merge_sort() function, and the sorted result is printed by the merge_sort_print() function.

def merge_sort_print():
    input1 = [5,48,95,74,65,32,56,58,65,32,8,6,4,5,25,64]
    print(input1) 
    sorted_list = merge_sort(input1) 
    print(sorted_list) 
merge_sort_print()

When the program runs, it prints the original list first and then shows the list after the Merge Sort algorithm has sorted it in ascending order.

Output:

Merge Sort Time Complexity

In the best, medium, and worst scenarios, Merge Sort's time complexity is O(n log n). The fact that Merge Sort performs consistently regardless of the arrangement of the input data is one of its key features.

Best Case: (n log n)

When the input list is already sorted, this is the ideal scenario. Merge Sort splits the list into smaller sublists and then combines them back together even though the elements are in the right order. The time complexity is still O(n log n) because it cannot establish that the list has already been sorted without completing these steps.

Average Case: O(n log n)

The elements in the list are often arranged randomly. Merge Sort merges the sorted sublists after splitting the list in half recursively. The total time complexity is O(n log n) as the list is divided log n times and each merging operation processes all n members.

Worst Case: (n log n)

The worst scenario is when the elements are placed in any order that necessitates the greatest number of comparisons during the merging process, or in reverse order. Merge Sort carries out the same number of divisions and merging operations even in this scenario. As a result, O(n log n) is also the worst-case time complexity.

Merge Sort Space Complexity

Merge Sort has an O(n) space complexity. This is due to the fact that while merging the split sublists back together, Merge Sort generates new temporary arrays (or lists). In contrast to certain in-place sorting algorithms, Merge Sort needs additional memory to hold these transient components while sorting.

Application of Merge Sort

Because of its known time complexity, stability, and effective performance, merge sort is frequently employed in computer science. Some of the most popular uses for Merge Sort are listed below:

1. Sorting Large Datasets

Because it ensures a time complexity of O(n log n), regardless of whether the data is previously sorted or entirely random, merge sort is a great option for sorting big collections of data.

2. External Sorting

Merge Sort is frequently used for external sorting when there is too much data to fit in the computer's main memory. It divides disk-stored data into smaller pieces, sorts each piece independently, and then combines the sorted files.

3. Linked List Sorting

One of the finest algorithms for sorting linked lists is merge sort. Merge Sort is a better option since linked lists may be split and merged effectively without the need for extra element moving, unlike arrays.

4. Stable Sorting Applications

Because Merge Sort maintains the relative order of elements with equal values, it is a stable sorting method. This makes it helpful in applications like sorting employee records, student records, or transaction data when it's crucial to preserve the original order of duplicate records.

5. Divide and Conquer Problems

Because Merge Sort exemplifies the Divide and Conquer strategy, it can be used to solve a variety of algorithmic issues that require recursively decomposing a problem into smaller subproblems.

Advantages of Merge Sort

In the best, medium, and worst scenarios, Merge Sort is an effective and dependable sorting algorithm that ensures a time complexity of O(n log n). Because it maintains the relative order of equal elements, it is a stable sorting algorithm. It is a common option in real-world applications because it is especially well suited for sorting big datasets, linked lists, and data kept on external storage devices.

Disadvantages of Merge Sort

The primary flaw in Merge Sort is that, to hold temporary arrays during the merging operation, O(n) more memory is needed. Compared to methods like Quick Sort or Heap Sort, it uses more memory because it is not an in-place sorting algorithm. Additionally, Merge Sort is less effective for sorting very tiny datasets due to the overhead introduced by the recursive function calls.

Conclusion

Based on the Divide and Conquer strategy, Merge Sort is one of the most effective and popular sorting algorithms. To create a fully sorted list, it recursively splits a list into smaller sublists, sorts them, and then combines them back together. Merge Sort is a great option for sorting big datasets and linked lists because of its steady sorting behavior and guaranteed O(n log n) time complexity in all scenarios. Its continuous performance and dependability make it a useful algorithm for both academic learning and practical applications, even if it consumes more memory during the merging process. A solid basis for learning other sophisticated algorithms and recursive problem-solving strategies is also provided by comprehending Merge Sort.

Next Steps

Explore the Bucket Sort algorithm.
Explore Selection Sort Algorithm.
Explore Quick Sort Algorithm.
Explore Heap sort Algorithm.
Explore Bubble Sort Algorithm.

Bucket Sort Algorithm

Achyut Tripathi — Mon, 03 Aug 2026 16:21:52 +0000

Bucket sort is a comparison-based sorting algorithm. A bucket sort is helpful when the input array is uniformly distributed. The bucket sort algorithm divides the unsorted array into several groups termed "buckets." When there are more than two values in the same bucket, they are sorted individually using any sorting algorithm, or bucket sort is used recursively. At last, all the individual buckets are combined to form a sorted array.

A distribution-based sorting method called bucket sort divides data into several categories known as buckets. Bucket Sort divides the components into many buckets according to their values rather than comparing each element with the others. After that, each bucket is sorted separately, typically using a different sorting algorithm like Insertion Sort or the built-in sorted() function in Python. The final sorted array is created by combining all of the sorted buckets.

When the input data is evenly distributed over a predetermined range, bucket sorting performs best. Although it may be modified for integers by employing a suitable bucket assignment approach, it is especially effective for sorting floating-point numbers between 0 and 1. Bucket Sort can perform exceptionally well for appropriate datasets since it reduces comparisons and sorts just small groups of elements.

Working Of Bucket Sort

Step 1: Initialize the Input Array

Suppose an input array of size 8 with floating-type values is given.

bash Arr = [0.47,0.29,0.23,0.66,0.35,0.42,0.51,0.59]

Step 2: Initialize the Buckets

Create an answer array of size 10, where each block (position) of the array is used as a bucket to sort the input array.

bash answer = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Indexes are followed from 0 to 9.

Step 3: Assign Elements to Buckets

Insert each element from the input array into the bucket according to its range. Here, the bucket range will be [0 to 1], [1 to 2], [2 to 3], [3 to... n-1].

Here, n is the number of elements in the array.

Step 3.1: First iteration

In our example, let's take the first element as 0.47. Multiply 0.47 by the size of the array. That is, 0.47*10 = 4.7. Approximately 4.7 is lying in the bucket whose index value is 4.So, finally, 0.47 is inserted into bucket 4.

The answer array is created after the first iteration.

bash answer= [0,0,0,0.47,0,0,0,0]

Step 3.2: Second iteration

Take the second element as 0.29. Multiply 0.29 by the size of the array. That is 0.29*10 = 2.9 (2.9 2). Approximately 2.9 lies in the bucket whose index value is 2.

So, finally, 0.29 is inserted into bucket 2. After the second iteration, the answer array is:

bash answer= [0,0,0.29,0,0.47,0,0,0,0]

Perform this operation until all elements are inserted into the bucket.

Step 3.3: Last iteration

The last iteration answer array looks like this-

bash Answer = [0,0, (0.29,0.23)], 0.35, (0.47,0.42)), (0.51,0.59)], 0.66,0,0,0]

Step 4: Sort the Elements in Each Bucket

The answer element of each bucket with more than two values is sorted using any sorting algorithm, or bucket sort is used recursively.

After this step, the answer array will look like this:

bash Answer = [0,0, (0.23,0.29),0.35, (0.42,0.47), (0.51,0.59), 0.66,0,0]

Step 5: Concatenate All Buckets

After collecting all the elements into each of the buckets, the final array will look like this:

bash Final = [0.23,0.29,0.35,0.42,0.47,0.51,0.59,0.66]

Return the final array. The final array is a sorted array

Bucket Sort Algorithm

1. Create N empty Bucket.
2. Do the following for every array element array[i].
      - insert array[i] into bucket [N*array[i]]
3. sort individual buckets using any of the sorting algorithms.
4. Combine and return all the sorted buckets.

Step 1: Create N Empty Buckets

bash Create N empty buckets.

First, make N empty buckets, where N is the input array's element count.

Elements that fall within a particular range of values are stored in each bucket.

At first, every bucket is empty. By dividing the data into smaller groupings, these buckets improve the efficiency of sorting.

Step 2: Insert Each Element into the Appropriate Bucket

bash For every array element array[i], insert array[i] into bucket[N × array[i]]

Go through each element in the input array one at a time.

Determine the bucket index for each element using:

N × array[i] is the bucket index. The bucket number is determined by the integer portion of this value.

Place the component in the appropriate bucket. The same bucket is used for elements with comparable values.

Step 3: Sort Individual Buckets

bash Sort individual buckets using any sorting algorithm.

Each bucket is sorted independently once all components have been distributed.
Sorting is not necessary if a bucket only has one element.

Use a sorting technique like this if a bucket has more than one element:
Insertion Sort
Quick Sort
Merge Sort
Python's sorted() function.

Step 4: Combine and Return All the Sorted Buckets

bash Combine and return all the sorted buckets.

From the first to the last bucket, visit each one.
Each bucket's sorted elements should be copied into the original array.
The final array is fully sorted as each bucket has previously been sorted and the buckets are processed sequentially.

Bucket Sort Code In Python

The next stage is to implement Bucket Sort in Python after comprehending its algorithm and operating concept. The program that follows shows how Bucket Sort generates buckets, assigns elements to each bucket, sorts each bucket separately, and then combines all of the buckets to make the sorted array. Floating-point values between 0 and 1 can be sorted using this technique.

Bucket Sort in Python


# Bucket Sort
def bucketsort(arr):
    bucket = []

    # Create empty buckets
    for i in range(len(arr)):
        bucket.append([])

    # Insert elements into their respective buckets
    for i in arr:
        index = int(10 * i)
        bucket[index].append(i)

    # Sort each bucket
    for i in range(len(arr)):
        bucket[i] = sorted(bucket[i])

    # Merge all buckets into the original array
    temp = 0
    for i in range(len(arr)):
        for j in range(len(bucket[i])):
            arr[temp] = bucket[i][j]
            temp += 1

    return arr


# Driver Code
arr = [0.47, 0.29, 0.23, 0.66, 0.35, 0.42, 0.51, 0.59]

print("Sorted array using Bucket Sort:")
print(bucketsort(arr))

Step 1: Define the Function and Create Empty Buckets

def bucketsort(arr):
    bucket = []

    for i in range(len(arr)):
        bucket.append([])

The input array is sorted using the bucketsort() function. The bucket is initialized as an empty list.

To store elements according to their values, a loop creates empty buckets—one bucket for each element in the array.

Step 2: Distribute Elements into Buckets

for i in arr:
    index = int(10 * i)
    bucket[index].append(i)

One by one, the input array's elements are processed.
The formula for the bucket index is int(10 * i).
Based on its value, the element is placed into the appropriate bucket.

Step 3: Sort Each Bucket

for i in range(len(arr)):
    bucket[i] = sorted(bucket[i])

Python's built-in sorted() method is used to sort each bucket separately.
Buckets with one or no elements stay the same.

Step 4: Merge the Sorted Buckets

temp = 0
for i in range(len(arr)):
    for j in range(len(bucket[i])):
        arr[temp] = bucket[i][j]
        temp += 1

Each bucket's sorted elements are replicated into the initial array.
The position in the original array is tracked by the variable temp.
This creates a single, fully sorted array from all of the buckets.

Step 5: Return the Sorted Array

return arr

Once all buckets have been combined, the function returns the final sorted array.

Step 6: Call the Function and Display the Output

arr = [0.47, 0.29, 0.23, 0.66, 0.35, 0.42, 0.51, 0.59]

print("Sorted array using Bucket Sort:")
print(bucketsort(arr))

It creates a floating-point input array.
The array is used as input when the bucketsort() function is called.
The sorted array is then printed.

Output

bash Sorted array using Bucket Sort: [0.23, 0.29, 0.35, 0.42, 0.47, 0.51, 0.59, 0.66]

Bucket Sort Code In Java

The Bucket Sort algorithm's implementation is shown in the Java program that follows. It makes several buckets, divides the input elements into the appropriate buckets according to their values, sorts each bucket separately, and then combines all of the buckets to produce the sorted array. This approach works well for sorting floating-point values between 0 and 1.

// Bucket sort in Java
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    @SuppressWarnings("unchecked")
    ArrayList<Float>[] bucket = new ArrayList[n];
    // Create empty buckets
    for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList<Float>();

    // Add elements into the buckets
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }
    // Sort the elements of each bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }
    // Get the sorted array
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }
  // Driver code
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,(float) 0.51 };
    b.bucketSort(arr, 7);
    for (float i : arr)
      System.out.print(i + "  ");
  }
}

Step 1: Import Required Libraries and Create the Class

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

Dynamic buckets are made with the ArrayList class.
Each bucket can be sorted using the sort() function provided by the Collections class.
The Bucket Sort algorithm is implemented in a class called BucketSort.

Step 2: Create Empty Buckets

ArrayList<Float>[] bucket = new ArrayList[n];

for (int i = 0; i < n; i++)
    bucket[i] = new ArrayList<Float>();

An array of ArrayList objects is created to represent the buckets.
A loop initializes each bucket as an empty ArrayList.
These buckets will store the input elements based on their values.

Step 3: Distribute Elements into Buckets

for (int i = 0; i < n; i++) {
    int bucketIndex = (int)(arr[i] * n);
    bucket[bucketIndex].add(arr[i]);
}

One by one, the input array's elements are processed.
Arr[i] * n is used to calculate the bucket index.
Based on its value, the element is placed into the appropriate bucket.

Step 4: Sort Each Bucket

for (int i = 0; i < n; i++) {
    Collections.sort(bucket[i]);
}

Each bucket is sorted individually using Java's built-in Collections.sort() method.
Buckets with zero or one element require little or no sorting.

Step 5: Merge the Sorted Buckets

int index = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < bucket[i].size(); j++) {
        arr[index++] = bucket[i].get(j);
    }
}

The sorted elements from all buckets are copied back into the original array.
The variable index keeps track of the current position in the array.
After merging, the original array becomes completely sorted.

Step 6: Execute and Display the Output

BucketSort b = new BucketSort();

float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};

b.bucketSort(arr, 7);

for (float i : arr)
    System.out.print(i + " ");

A BucketSort class object is generated.
Unsorted values are used to initialize a float array.
The array is sorted by calling the bucketSort() function.
The sorted elements are then displayed on the screen.

Output

0.32  0.33  0.37  0.42  0.47  0.51  0.52

Bucket Sort Time Complexity

1. Best-Case - O(n+k)

When the elements of the input array are uniformly distributed over the buckets, each bucket has either an equal or nearly equal number of elements.

The time required to make the bucket is denoted by O(n), and O(k) is the amount of time it takes to sort the elements. So the total time complexity of the best case is O (n+k).

2. Average-Case - O(n*n)

When the elements of the input array are distributed randomly over the buckets, then the time complexity is linear. Even if the elements of the input array are not uniformly distributed over the buckets, bucket sort runs in linear time. So the total time complexity of the average case is O (n).

3. Worst-Case - O(n^2)

The worst case occurs when all the elements are placed into the same bucket. This happens when the input values are very close to each other or the bucket distribution is poor. In this situation, Bucket Sort loses its advantage because one bucket contains almost all the elements.

The overall time complexity then depends on the sorting algorithm used to sort that bucket. If Insertion Sort is used and the elements are in reverse order, sorting that bucket takes O(n²) time. Therefore, the worst-case time complexity of Bucket Sort is O(n²).

Application

Floating-Point Number Sorting

Floating-point numbers are frequently sorted using bucket sort, particularly when the values fall within a predetermined range like 0 to 1.

Systems for Database Management

Large datasets can be effectively sorted and organized with it, speeding up data retrieval and searches.

Data Processing and Analytics

For statistical analysis and reporting, bucket sort aids in the grouping and sorting of numerical data.

Computing in Science

It is employed in scientific applications when it is necessary to swiftly sort big collections of consistently dispersed numerical values.

Analysis of Frequency and Histograms

When creating histograms and analyzing data distributions, bucket sorting is helpful for organizing values into intervals, or buckets.

Processing in parallel

Bucket Sort is ideal for distributed and parallel computing systems since each bucket can be sorted individually.

Graphics on Computers

When the data falls inside a predetermined range, it is utilized in graphics programs to effectively sort objects or depth values.

Large Uniformly Distributed Datasets

Bucket Sort is appropriate for many real-world applications because it works well with huge datasets whose values are evenly distributed.

Conclusion

When the input elements are evenly distributed throughout a predetermined range, Bucket Sort, an effective non-comparison sorting technique, works well. To create the final sorted array, it divides the elements into several buckets, sorts each bucket separately, and then merges the sorted buckets.

When the input values are uniformly distributed, Bucket Sort performs exceptionally well for huge datasets, with an average and best-case time complexity of O(n + k). Although it can be modified for other ranges by employing an appropriate bucket assignment technique, it is most useful for sorting floating-point numbers in the range of 0 to 1.

However, the distribution of the items throughout the buckets determines how well Bucket Sort performs. Depending on the sorting method employed within each bucket, the algorithm's performance declines and the worst-case time complexity becomes O(n²) if the majority of elements fall into one bucket.

In applications like data analysis, database systems, scientific computing, and parallel processing, when the input range is known and the data is roughly evenly distributed, bucket sort is a straightforward, quick, and effective sorting method for appropriate datasets.

DEV Community: Achyut Tripathi

Stack and Queue in Python

Stack

Operations of Stack

The time complexity of a stack

When are stacks useful?

How does create your own stack

Output

Implementing stacks as arrays versus linked lists

Output

Queue

Operations of Queue

Time complexity of a stack

When are queues useful?

How to create your own Queue

Output

Implementing Queue as arrays versus linked list

Building up a Queue

Output

Conclusion

DDL(Data Definition Language) Statements in PostgreSQL

PostgreSQL Create Table

Syntax:-

Output-

Output-

\d Command in Postgres

Syntax:-

Example:-

Output-

“\d tablename” Command in Postgres

Syntax:-

Example:-

Output-

Exapmple-

Output-

PostgreSQL Drop Table

Syntax:-

Example:-

Output:-

PostgreSQL Alter Table

Syntax:-

Add columns in table using Alter

Syntax:-

Example:-

Output:-

Add multiple columns in table using Alter

Syntax:-

Example:-

Output:-

Drop columns in table using Alter

Syntax:-

Example:-

Output:-

Modify columns in table using Alter

Syntax:-

Example:-

Output:-

Rename columns in table using Alter

Syntax:-

Example:-

Output:-

Rename Table in table using Alter

Syntax:-

Example:-

Output:-

PostgreSQL Truncate Table

Syntax:-

Example:-

Output:-

Truncate data over multiple table

Syntax:-

Example:-

Output:-

Conclusion

Next Steps

Normalization in SQL

Problem with an unnormalized database

Insertion anomalies

Example

Deletion anomalies